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