2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Priority method gets used a lot in computability theory - see some of the later chapters of Soare's book on computability.

Buhrman and Torenvliet 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". Generic oracles get used a lot.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer $\endgroup$
    – XL _At_Here_There
    Sep 7, 2022 at 4:33

Your Answer

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

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