3
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ There is no argument there. Only setup. Whether such $N$ exists depends on the classes, it's probably not universally true. $\endgroup$ – Raphael Aug 6 '14 at 7:21
  • $\begingroup$ this seems kind of abstract. what are the 2 models of computation? $\endgroup$ – vzn Aug 7 '14 at 14:54
3
$\begingroup$

You can indeed assume that you know a polynomial bound on the time it takes to compute a polytime function. This is an example of a non-constructive argument.

The down side is that you won't be able to construct a computable function transforming polytime function of one model to the other. In some situations (say a diagonal argument) this is needed, and then the trick is to assume that programs are clocked, i.e. come with their own time bounds. This makes sense in that application since we can enumerate all polytime functions as computed by polynomially clocked machines. In your case, however, you don't need to worry about such issues.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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