I have a (stupid ?) question about complexity theory. It's about a proof technique.I want to compare 2 models of computation. I want to prove that for each langage recognized in polynomial time by a machine of the first model, there exists a machine of the second class that recognizes the same langage in polynomial time. Can I use this argument in my proof : Let M be a machine of the first class that recognizes a langage L in time T(n) (where T is a polynomial, and n the size of the input word). Let N be a machine of the second class that is able to computes T(n) ...The idea is to use the knowledge of T(n) to have a bound on the space used on each input by the machine of the first class, which that makes the construction of the machine of the second class easier. However, it seems a bit strange to say that we explicitly know T(n)... Is it allowed ?
Proof technique in complexity theory
complexity theory;proof techniques;simulation