1
$\begingroup$

Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return True or False and will not diverge by e.g. looping forever, exhibiting undefined behavior, or crashing. This is equivalent to determining if a Turing machine with one accepting and one rejecting state, and which is guaranteed to reach one of these states eventually, will reach the accepting state.

This problem seems to trivially break the (relativized) Time Hierarchy Theorem, for $R^{PE}$ = $P^{PE}$ = R by direct simulation. What makes PE act in this way?

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ It's not really clear what the question is. This site is generally for well-defined mathematical questions that admit a definite answer. "Why is ..." is something my kids say a lot, but it's hard to guess what it means. Are you asking for a proof that the time hierarchy theorem fails relative to PE? You already know that. Are you asking why the standard proof of the time hierarchy theorem does not apply with a promise problem oracle? This is easy to see: the proof constructs a language by diagonalization, throwing arbitrary inputs at arbitrary clocked machines with the right time bound, ... $\endgroup$
    – Emil Jeřábek
    Commented Mar 4 at 10:31
  • 1
    $\begingroup$ ... and this will violate the promise sooner or later. Are you asking for something else? You need to formulate it clearly and unambiguously so that it's clear what would constitute a valid answer. $\endgroup$
    – Emil Jeřábek
    Commented Mar 4 at 10:35
  • $\begingroup$ @EmilJeřábek Ah right I was thinking P^PE vs RE (rather than R). Thanks for pointing this out! I deleted my comment as it was a silly mistake that doesn't add to the convo. $\endgroup$
    – Joshua Grochow
    Commented Mar 4 at 15:56
  • $\begingroup$ Resource hierarchy theorems rely on synthetic enumeration and simulation typically. If you cannot enumerate and simulate you can do diagonalization to prove the theorem. When you add a promise to a model, you may not be able to enumerate a list of representatives for languages in the complexity class. $\endgroup$
    – Kaveh
    Commented Mar 5 at 1:44
  • $\begingroup$ The promise you have here is not decidable, so you cannot enumerate them to do a effective diagonalization, to prove a resource hierarchy theorem for them. $\endgroup$
    – Kaveh
    Commented Mar 5 at 1:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.