2
$\begingroup$

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?
Improve this question
$\endgroup$
2
  • $\begingroup$ I only answered your first question since the meaning of "reduction" is unclear for second question. $\endgroup$
    – François G. Dorais
    Commented Nov 10, 2011 at 21:34
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Feb 21, 2012 at 1:56

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – rajeshsr
    Commented Dec 26, 2011 at 19:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .