Hot answers tagged

4

As the original paper is showing a lot more, I use this one at page 69-70, Theorem 3.9, as this is the proof I also know. As you can see there, the complete statement of Baker, Gill, Solovay is: There exist oracles $A, B$ s.t. $P^A = NP^A$ and $P^B \neq NP^B$ The second oracle cannot be considered a counterexample for $P = NP$ because you cannot "...


3

At best, the evidence given is only heuristic and informal, but it is still important. Oracles in the examples you gave do address the general question: how does quantum computing compare to nondeterminism and randomness, in power? The oracles definitely do not answer the original unrelativized questions, rather they provide a different (related) black-box ...


2

Let us consider the following decision version of your first problem: Given a SAT instance, does its multilinear representation have a term of degree at most $d$? I claim that this is the case iff the SAT instance has a satisfying assignment with at most $d$ ones. Indeed, suppose first that $m$ is an inclusion-minimal term in the multilinear ...


2

It can hardly be considered evidence for inequality or equality. We know $\mathsf{IP} = \mathsf{PSPACE}$, but there is an oracle $A$ relative to which $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$ (as proved here). Similarly, there are classes which are not equal, even though their relativized versions to a certain oracle are equal (see here for a couple examples). ...


1

The answer to all of those questions is no, and not for some especially deep reason, as most of these can be ruled out by forcing the intersection to be simple enough. Suppose $B$ contains all languages with only even length words, and $C$ contains all languages with odd length words. Clearly $B\cap C =\emptyset$, so $\mathsf{P^{B\cap C}=P}$, but $P^B, P^C$ ...


1

There are no general tricks for proving self lowness, note that the classes that you yourself mentioned are very different in nature. Recall that $L\in P/poly$ iff there exists a Turing machine $M(x,y)$, which runs in time polynomial in $|x|$, and an advice sequence $\{\alpha_n\}_{n\in\mathbb{N}}$, such that for all $x\in\Sigma^*$ it holds that: $x\in L \...


Only top voted, non community-wiki answers of a minimum length are eligible