Is an enumerable multicomponent class of functions recursive?

Question

If I define Poly-time functions, the functions that the turing machine calculates at the maximum polynomial (n) time, n is the input size. Is the class of these functions recursively enumerable?

Answer 1

I am sure that the answer is no. The program for recursively listing Poly-time functions should at some point tell you whether the function that solves the traveling salesman problem is Poly-time. Regardless of whether this particular question answers, at this time it is still open.

I do not know that I smoked with this terrible answer. If the salesman problem is not poly-time, the program should never detect this fact. It just doesn't have to get around to listing any solutions for this. It is easy because he will never find it.

One important detail that I don't understand about is how you represent functions and what you consider to be a unique function.

Suppose that the function is equal to a "program running in Poly-time mode", and you want to list all the programs, regardless of whether they produce the same output. Then your answer comes down to: "If the given program is Time, is there always evidence of this fact?" This is clearly false. You may have a program that looks for polynomial time to prove some open-ended question, and if it finds it, it spends exponential time before releasing the final output. This program has a lot of time, but you cannot prove it without proving that the open question is incorrect.

Suppose a function is “a rule that connects inputs to outputs” for you, and you’re out of order with a list of several programs that encode the same function. Let's modify the previous pathological function to change its output, and not waste time if evidence is found. Now you can prove that this program has a lot of time, but you cannot prove whether it represents a different function than the one that does not perform the entire step of the proof (and possibly modifies its output).

Suppose a function is “a rule that connects inputs to outputs” for you, and you are fine with a list of several programs that encode the same function, but don’t want each one to be enabled. Suppose prog is a program that may or may not be poly time, and p(x) is a polynomial. It is easy to write a second program that emulates the first step p(x) , and if the other still works, some fixed output is emitted. This second program is guaranteed to be poly time. If, in fact, prog is a poly-time, then some program of this form will represent the same function as prog , and therefore the list of exits will include all possible polyfunctions. (But the same function will be encoded in many different ways.)

Answer 2

Well, the answer seems no, look at the diagram in the complexity class .

Answer 3

Answer: yes, in fact I also found evidence in the book. Thanks to everyone, they helped me a lot with the indicated directions :)

Answer 4

It is relatively easy to give an enumeration for all functions calculated at polynomial time: just give an enumeration pi_j for all polynomials, for j to N, and then consider for any pair (i, j) a machine that works like a Turing Machine M_i with a clock pi_j. Any function that can be calculated in polynomial time can be expressed in this way.

This is very different from the problem, in order to understand if the universal Turing machine works in polynomial time, which is not solvable. The proof is not trivial, since it is not an extensional property of programs, and we cannot apply Rice's theorem. You can find the proof in my article Intensive Content of Rice's Theorem, POPL 2008 (pearl).

The problem of providing syntactic characteristics of subrecursive complexity classes, such as P, Pspace, etc., has received much attention in the literature. The recent area of ​​Implicit Complexity is aimed at studying the computational complexity of programs without reference to a specific machine model and explicit restrictions on time or memory, but instead relying on logical or computational principles that entail properties of complexity, usually through controlled use available resources. To familiarize yourself with this topic, you can refer to the special issue of Implicit Computational Complexity, ACM Trans. Subtract. Journal., Volume 10, n.4 2009.

Other interesting characteristics were obtained that limited the interpretation of programming languages ​​to finite areas. The original Result of this area is Gurevich’s old work (“Algebras of Admissible Functions”, FOCS 1983), where he proved that the interpretation of primitive recursive functions (respectively recursive functions) on finite structures accurately obtains the log space (respectively polynomial time) of computable functions.

Please take a look at my article, Computational Complexity Through Finite Types, ACM Trans. Subtract. Log., Vol. 16, n.15 2015, for additional references in this area.