The computation of rational homotopy groups is #\(\wp\)-hard. (English) Zbl 0691.55009
Computers in geometry and topology, Proc. Conf., Chicago/Ill. 1986, Lect. Notes Pure Appl. Math. 114, 1-56 (1989).
[For the entire collection see Zbl 0656.00021.]
The aim of this article is to investigate the theoretical computational complexity of rational homotopy groups. It is written for topologists, and requires no prior familiarity with theoretical computer science concepts. In the whole article, all functions are those defined on a set of natural numbers and whose values are natural numbers. A function f is said to be computable in polynomial (exponential) time if there exists a deterministic Turing machine and a polynomial \(\tau\) (x) such that for any input \(N\in dom(f)\) the output is f(N) and the total number of steps needed is bounded above by \(\tau\) (\(\ell (N))\) \((2^{\tau (\ell (N))})\), where \(\ell (N)\) is the length of the input N. A function f is said to belong to the class #\(\wp\) if there exists a nondeterministic Turing machine and a polynomial \(\tau\) (x) such that for any \(N\in dom(f)\) each of the possible paths taken by the machine reaches the terminal state within \(\tau\) (\(\ell (N))\) steps, and the number of possible paths which lead to the fixed terminal state equals f(N). Let f, g be functions; function g is called Turing reducible to f, written \(g\leq_{T}f\), if there exists a deterministic Turing machine with an oracle which looks up f-values, and the machine computes the values of g in polynomial time using the f-values. A function f is said to be #\(\wp\)-hard if any \(g\in \#\wp\) is Turing reducible to f. The functions f, g are said to be Turing equivalent if \(f\leq_{T}g\), \(g\leq_{T}f.\)
The author considers the problem “to determine \(\dim_ Q(\pi_{n+1}(X)\otimes {\mathbb{Q}})'',\) where X is a finite, simply connected CW-complex. From the point of view of computer science it is advantageous to relate it with other problem as, e.g., “find the n-th term of the Hilbert sequence of a finitely presented connected graded \({\mathbb{Q}}\)-algebra”, “find the n-th entry in the Poincaré-Betti sequence of a finite-dimensional basic local \({\mathbb{Q}}\)-algebra”. He proves that all these problems (alltogether, there are 12 of them) are Turing equivalent to one another and that they are #\(\wp\)-hard. He shows also that each of them is computable in exponential time.
The aim of this article is to investigate the theoretical computational complexity of rational homotopy groups. It is written for topologists, and requires no prior familiarity with theoretical computer science concepts. In the whole article, all functions are those defined on a set of natural numbers and whose values are natural numbers. A function f is said to be computable in polynomial (exponential) time if there exists a deterministic Turing machine and a polynomial \(\tau\) (x) such that for any input \(N\in dom(f)\) the output is f(N) and the total number of steps needed is bounded above by \(\tau\) (\(\ell (N))\) \((2^{\tau (\ell (N))})\), where \(\ell (N)\) is the length of the input N. A function f is said to belong to the class #\(\wp\) if there exists a nondeterministic Turing machine and a polynomial \(\tau\) (x) such that for any \(N\in dom(f)\) each of the possible paths taken by the machine reaches the terminal state within \(\tau\) (\(\ell (N))\) steps, and the number of possible paths which lead to the fixed terminal state equals f(N). Let f, g be functions; function g is called Turing reducible to f, written \(g\leq_{T}f\), if there exists a deterministic Turing machine with an oracle which looks up f-values, and the machine computes the values of g in polynomial time using the f-values. A function f is said to be #\(\wp\)-hard if any \(g\in \#\wp\) is Turing reducible to f. The functions f, g are said to be Turing equivalent if \(f\leq_{T}g\), \(g\leq_{T}f.\)
The author considers the problem “to determine \(\dim_ Q(\pi_{n+1}(X)\otimes {\mathbb{Q}})'',\) where X is a finite, simply connected CW-complex. From the point of view of computer science it is advantageous to relate it with other problem as, e.g., “find the n-th term of the Hilbert sequence of a finitely presented connected graded \({\mathbb{Q}}\)-algebra”, “find the n-th entry in the Poincaré-Betti sequence of a finite-dimensional basic local \({\mathbb{Q}}\)-algebra”. He proves that all these problems (alltogether, there are 12 of them) are Turing equivalent to one another and that they are #\(\wp\)-hard. He shows also that each of them is computable in exponential time.
Reviewer: J.Vanzura
