Generic oracles, uniform machines, and codes (Q1184732): Difference between revisions

This paper proves primarily the theorem that a nondeterministic oracle machine which for any oracle \(X\) accepts the tautologies relativized to \(X\) when running with oracle \(X\) does not run in polynomial time at any oracle. It is also shown that if \(X\) is \(r\)-generic, and no nondeterministic machine with oracle \(X\) accepts the \(r\)-query tautologies relativized to \(X\) in polynomial time, then \(NP\neq \text{co}NP\). In addition, some properties of circuits as a model of computation of the Boolean functions are given.