<p>Priority method gets used a lot in computability theory - see some of the later chapters of <a href="https://doi.org/10.1007/978-3-642-31933-4" rel="noreferrer">Soare's book on computability</a>.</p>
<p><a href="https://doi.org/10.1007/3-540-58201-0_74" rel="noreferrer">Buhrman and Torenvliet</a> use a resource-bounded priority method to build an oracle <span class="math-container">$A$</span> such that <span class="math-container">$NEXP^A \subseteq P^{NP^A}$</span>.</p>
<p>Forcing is used in complexity theory in the construction of generic oracles. See, for example, <a href="https://doi.org/10.1016/S0890-5401(03)00018-X" rel="noreferrer">Fenner-Fortnow-Kurtz-Li, &quot;An oracle builder's toolkit&quot;</a>. Generic oracles get used a lot.</p>

CC BY-SA 4.0
2022-09-07T04:33:51.867Z
Thank you for your answer
XL _At_Here_There
CC BY-SA 4.0
2022-09-07T03:33:45.053Z
2022-09-07T03:33:45.053Z
Joshua Grochow
<p>As we know, there are many questions of Turing Degree closed by injury priority method. Is any computational complexity question solved by injury priority method except Post problem or Turing Degree?</p>
<p>I'm curious about how to solve by same or similiar methods the parallel questions up and down the computational hierarchy</p>
<p>BTW，any question in computer science is solved by forcing except continuum hypothesis?</p>

<cc.complexity-theory><set-theory><recursion>
Is any computational complexity question solved by injury priority method except Post problem?
XL _At_Here_There
# Is any computational complexity question solved by injury priority method except Post problem?

(Asked by: username_0 on 2022-09-07)

As we know, there are many questions of Turing Degree closed by injury priority method. Is any computational complexity question solved by injury priority method except Post problem or Turing Degree?

I'm curious about how to solve by same or similiar methods the parallel questions up and down the computational hierarchy

BTW，any question in computer science is solved by forcing except continuum hypothesis?

**Tags:** cc.complexity-theory, set-theory, recursion

---

## 1 answers

### Answer by username_1 on 2022-09-07. Score: 5 | Accepted answer

Priority method gets used a lot in computability theory - see some of the later chapters of [Soare's book on computability](https://doi.org/10.1007/978-3-642-31933-4).

[Buhrman and Torenvliet](https://doi.org/10.1007/3-540-58201-0_74) use a resource-bounded priority method to build an oracle $A$ such that $NEXP^A \subseteq P^{NP^A}$.

Forcing is used in complexity theory in the construction of generic oracles. See, for example, [Fenner-Fortnow-Kurtz-Li, "An oracle builder's toolkit"](https://doi.org/10.1016/S0890-5401(03)00018-X). Generic oracles get used a lot.

> **Comments:**
> **username_0**: Thank you for your answer  

---

