Skip to main content
5 votes
Accepted

Does $NP^{SAT}=NP^{NP}$?

Yes, because $\mathsf{SAT}$ is $\mathsf{NP}$-complete. Let $L\in\mathsf{NP}^\mathsf{NP}$. This means that there exists $A\in\mathsf{NP}$ such that $L\in\mathsf{NP}^A$. But you can replace any oracle ...
Evangelos Bampas's user avatar
5 votes

Why are Oracle Separations Counted as Evidence toward Unconditional Separation?

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 ...
dkaeae's user avatar
  • 5,027
5 votes

Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B

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: ...
Niklas Wünsche's user avatar
3 votes

Why are Oracle Separations Counted as Evidence toward Unconditional Separation?

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 ...
Ryan Williams's user avatar
3 votes
Accepted

Is $A \leqslant_P B \iff A \in \mathsf{P}^B$? If not are there counter-examples?

Assuming $\le_P$ is a polynomial many-one reduction (as opposed to a Turing reduction), the statement is incorrect. For example, for any language $L$ we have $\overline{L} \in P^L$ (and in fact, in $O(...
nir shahar's user avatar
  • 11.6k
2 votes

Can quantum computers be modelled as a classical computer with access to an oracle?

Vacuous answer: because $\text{BPP}^\text{BQP} = \text{BQP}$, giving a computer access to a $\text{BQP}$ oracle makes it equivalent to a quantum computer at solving decision problems in polynomial ...
Craig Gidney's user avatar
  • 5,862
2 votes
Accepted

For all oracles A, If $P^A \neq PSPACE^A$, then Does it imply that $P \neq PSPACE$?

If $A = \emptyset$, or more generally, if $A \in \mathsf{P}$, then $\mathsf{P}^A = \mathsf{P}$ and $\mathsf{PSPACE}^A = \mathsf{PSPACE}$, and so $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ is the same as $\...
Yuval Filmus's user avatar
2 votes
Accepted

Oracle query’s required

Your problem is #P-hard. Indeed, given a #SAT instance with variables $x_i$ and clauses $C_j$, let $\kappa_{i,b}$ be the product of the clauses $C_j$ satisfied by the truth assignment $x_i=b$, and ...
Yuval Filmus's user avatar
2 votes
Accepted

Algorithm for idempotent algebra

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 ...
Yuval Filmus's user avatar
1 vote

Making statements about quantum complexity theory

Shor's algorithm does not use an oracle. The input is a number $n$ to be factored. $U$ is not an oracle; it is a computation that is done by the algorithm (akin to a subroutine).
D.W.'s user avatar
  • 162k
1 vote
Accepted

How to define the languages of the implicit set system problems?

There are different notions of complexity used for various computational problems, not all tasks fit naturally to the standard model of decision/search problems. The "classic" analysis of ...
Ariel's user avatar
  • 13.4k
1 vote

Can quantum computers be modelled as a classical computer with access to an oracle?

Technically, the main differences between classical and quantum algorithms are super-position and entanglement that make the concept of oracle in quantum algorithms. As these two are only meaningful ...
OmG's user avatar
  • 3,572
1 vote
Accepted

Oracle that can only definitively say if an instance is unsatisfiable

You can use your oracle to construct a process that is guaranteed to be correct, and will most likely be fast. The basic idea is that a proof that a formula is unsatisfiable might be huge - but if ...
Arno's user avatar
  • 3,183
1 vote

Oracle that can only definitively say if an instance is unsatisfiable

Edit: I wrongly read the question, therefore the following answer is incorrect. It would be correct if the oracle worked as followed: "if the instance is unsatisfiable, then the oracle always ...
Nathaniel's user avatar
  • 15.8k
1 vote
Accepted

Manipulating Intersection of oracles

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 ...
Ariel's user avatar
  • 13.4k
1 vote

$P/poly$ as oracle to itself?

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)...
Ariel's user avatar
  • 13.4k

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