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?

$\endgroup$

1 Answer 1

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer $\endgroup$ Sep 7 at 4:33

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.