MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi all, 1. Has there been any work done on trying to distinguish between different Polynomial Time Hierarchies say, O(n) vs O(n^2) problem? May be Turing Machine is too general for that. May be the way to go about doing it, is to make some algebraic structure which gives insights into it?

  1. Is there a notion of O(p(n))-Complete problem. That's it's a O(p(n)) problem and all problems computable in O(p(n)) can be reduced to it? Or it can be proved to be impossible?
share|cite|improve this question
I only answered your first question since the meaning of "reduction" is unclear for second question. – François G. Dorais Nov 10 '11 at 21:34
Note that one of nice things about polynomial time is that polynomials are closed under composition. This helps a lot in robustness of the definition of the complexity class $\mathsf{P}$ particularly regarding reductions. If the class is not closed under composition it is not going to be a very robust class. – Kaveh Feb 21 '12 at 1:56

Yes, of course! You might be interested in the Time Hierarchy Theorem, which says that if $f(n)$ is time constructible, then problems computable in time $O(f(n))$ are a proper superset of problems computable in time $o(f(n)/\log f(n))$ using a deterministic Turing machine with at least two tapes. In particular, you can do more in quadratic time than you can do in linear time on such machines.

Note, however, that the precise computational model will impact what particular problems are computable in time $O(f(n))$; not all time classes are as robust as polynomial time. The Time Hierarchy Theorem takes a slightly different form for deterministic Turing machines with one tape, nondeterministic Turing machines, and other computational models.

share|cite|improve this answer
Hi Dorais, I do know about the Time Hierarchy Theorem. I was looking at a discrimination along the lines of NP-Complete vs NP or even Recursive Enumerable vs Halting Problem (can be called RE-complete as languages in RE can be expressed by this.) But, yeah, I somehow forgot the notion of computational model which heavily influences Polynomial time. So, the conclusion can be no interesting structure can be constructed out of Polynomial space without a concrete computational model under consideration(and therefore quite uninteresting because of lack of generality!) right? – rajeshsr Dec 26 '11 at 19:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.