Skip to main content

# Tag Info

## Hot answers tagged oracles

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 ...
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 ...
• 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: ...
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 ...
3 votes
Accepted

• 278k
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 ...
• 278k
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 ...
• 278k
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).
• 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 ...
• 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 ...
• 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 ...
• 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 ...
• 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 ...
• 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)...
• 13.4k

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