# Structure of class P

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?
-
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.