<p>Define <em>Program Evaluation (PE)</em> to be the promise problem of determining whether a program (written in a Turing-complete language) returns <em>True</em> or <em>False</em>.  The promise is that the program <em>will</em> return <em>True</em> or <em>False</em> 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.</p>
<p>This problem seems to trivially break the (relativized) Time Hierarchy Theorem, for <span class="math-container">$R^{PE}$</span> = <span class="math-container">$P^{PE}$</span> = R by direct simulation.  What makes PE act in this way?</p>

CC BY-SA 4.0
2024-03-04T10:31:58.543Z
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, ...
Emil Jeřábek
CC BY-SA 4.0
2024-03-04T10:35:24.073Z
... 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.
Emil Jeřábek
CC BY-SA 4.0
2024-03-04T15:56:20.130Z
@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.
Joshua Grochow
CC BY-SA 4.0
2024-03-05T01:44:16.800Z
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.
Kaveh
CC BY-SA 4.0
2024-03-05T01:48:38.177Z
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.
Kaveh
CC BY-SA 4.0
2024-03-05T01:51:52.733Z
In addition, relativization is NOT an operator on arbitrary classes of languages, it is dependent on the machine model and how you give it access to the Oracle languages.
Kaveh
CC BY-SA 4.0
2024-03-05T02:00:01.310Z
Finally, consider the case of halting problem as an Oracle (with the standard way of defining it).  Within AC0 (and even weaker classes), for any TM M, you can construct the mapping taking that x and encoding it to <M,x> as input to H. I.e. you get the closure of computable languages over H. Whatever extra computale stuff you add to that base class will not change the result.
Kaveh
CC BY-SA 4.0
2024-03-05T02:06:17.040Z
Your PE is like H essentially. One more thing: separation theorems do NOT relativize, e.g. L != PSpace, but L^PSpace = PSpace^PSpace.
Kaveh
CC BY-SA 4.0
2024-03-05T08:13:24.590Z
@Kaveh The space hierarchy theorem, just like the time hierarchy theorem, should relativize if you state it right. Your last claim is shameless cheating, as you use different definitions of relativized space on either side (the query tape does not count towards the space bound on the left-hand side, but it does count on the right-hand side). If you use the same definition for both, they will be unequal.
Emil Jeřábek
CC BY-SA 4.0
2024-03-05T08:20:28.233Z
Though I should stress that the theorems relativize only if given a *single* oracle. The classes may well collapse when given a class of oracles (e.g., $\mathrm{P^R=R^R}$). This does not matter for the PSPACE examples they are almost equivalent to using a QBF oracle.
Emil Jeřábek
CC BY-SA 4.0
2024-03-09T00:40:09.693Z
@EmilJeřábek one can argue about how to relativize classes ad infinitum, I don't think there is a "right" one really. See my previous comments. I am using pretty common meanings of those two relativized classes. If you ask someone what is PSpace^PSpace and what is L^PSpace from people you will get the answer PSpace typically.
Kaveh
CC BY-SA 4.0
2024-03-09T00:50:40.363Z
ps: you can disagree without being disrespectful. There is no place to use loaded words like "shameless cheating" here.
Kaveh
CC BY-SA 4.0
2024-03-09T08:01:44.853Z
Oh my. That was a *joke*, Kaveh. I'm sorry if I offended your feelings. But I stand behind the technical content of my comment  You can relativize individual classes any way you see fit, but it does not make sense to claim something about relativized separation unless the two classes being separated are relativized in a compatible way.
Emil Jeřábek
<cc.complexity-theory><computability><hierarchy-theorems>
Why does the Time Hierarchy Theorem fail relative to promise problems?
Demi
# Why does the Time Hierarchy Theorem fail relative to promise problems?

(Asked by: username_0 on 2024-03-03)

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?

**Tags:** cc.complexity-theory, computability, hierarchy-theorems
> **Comments:**
> **username_1**: 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, ...  
> **username_1**: ... 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.  
> **username_2**: @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.  
> **username_3**: 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.  
> **username_3**: 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.  
> **username_3**: In addition, relativization is NOT an operator on arbitrary classes of languages, it is dependent on the machine model and how you give it access to the Oracle languages.  
> **username_3**: Finally, consider the case of halting problem as an Oracle (with the standard way of defining it).  Within AC0 (and even weaker classes), for any TM M, you can construct the mapping taking that x and encoding it to <M,x> as input to H. I.e. you get the closure of computable languages over H. Whatever extra computale stuff you add to that base class will not change the result.  
> **username_3**: Your PE is like H essentially. One more thing: separation theorems do NOT relativize, e.g. L != PSpace, but L^PSpace = PSpace^PSpace.  
> **username_1**: @Kaveh The space hierarchy theorem, just like the time hierarchy theorem, should relativize if you state it right. Your last claim is shameless cheating, as you use different definitions of relativized space on either side (the query tape does not count towards the space bound on the left-hand side, but it does count on the right-hand side). If you use the same definition for both, they will be unequal.  
> **username_1**: Though I should stress that the theorems relativize only if given a *single* oracle. The classes may well collapse when given a class of oracles (e.g., $\mathrm{P^R=R^R}$). This does not matter for the PSPACE examples they are almost equivalent to using a QBF oracle.  
> **username_3**: @EmilJeřábek one can argue about how to relativize classes ad infinitum, I don't think there is a "right" one really. See my previous comments. I am using pretty common meanings of those two relativized classes. If you ask someone what is PSpace^PSpace and what is L^PSpace from people you will get the answer PSpace typically.  
> **username_3**: ps: you can disagree without being disrespectful. There is no place to use loaded words like "shameless cheating" here.  
> **username_1**: Oh my. That was a *joke*, Kaveh. I'm sorry if I offended your feelings. But I stand behind the technical content of my comment  You can relativize individual classes any way you see fit, but it does not make sense to claim something about relativized separation unless the two classes being separated are relativized in a compatible way.  

---

## 0 answers

