Skip to main content

# Tag Info

## Hot answers tagged oracles

30 votes
Accepted

### Oracle Construction for Grover's Algorithm

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: ...
• 1,518
13 votes
Accepted

### Is there a good notion of non-termination and halting proofs in type theory?

Because one of the principal applications of Type Theory in formalizations has been to study programing languages and computation in general, a lot of thought has gone into ways of representing ...
• 13.9k
11 votes
Accepted

### Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below). We want ...
• 2,768
9 votes
Accepted

### What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any ...
• 37.4k
8 votes
Accepted

### Is there a simplex-like algorithm that can be used with a separation oracle?

I'm not sure if you would consider the algorithms I'll discuss here "Simplex-like" (but see the comment about column generation at the end). If you have a weak separation oracle for a ...
• 10.8k
8 votes
Accepted

### It is known that $L \subsetneq PH$?

This is equivalent to $LOGSPACE≠NP$ (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models). And there are oracles making $LOGSPACE = NP$ (the ...
• 27.5k
8 votes
Accepted

### Is $UP\not=NP$ with respect to random oracle?

Yes. Beigel CCC '89 showed $\mathsf{P} \neq \mathsf{UP} \neq \mathsf{NP}$ with probability 1. Combined with Rossman-Servedio-Tan, this gives the result you want. You should always try the Complexity ...
• 37.4k
8 votes
Accepted

### What can we do with a generic oracle (as opposed to a random one)?

In fact, GenericallyP = P: Proposition. The following are equivalent for any language $L$: $L\in\mathbf P$. $L\in\mathbf{GenericallyP}$. $\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}$ is not meager. ...
• 17.8k
7 votes

• 987
4 votes
Accepted

### Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

This is quite unlikely to hold, because $\mathrm{EXP_{poly}^{NEXP}}$ actually coincides with $\Theta^{\exp}_2$, the exponential analogue of the class $\Theta^P_2$, which is presumably a strict ...
• 17.8k
4 votes
Accepted

Such an $H$ would let us solve the halting problem: We begin by running $H(H(P))$ until it halts (which it does by assumption on $H$). If the output of $H(H(P))$ is "doesn't halt," then we know $H(P)... 3 votes Accepted ### Young Diagrams and distinguishing between two distributions Even relaxing the "computationally efficient" requirement, it is information-theoretically impossible. We will use the following "folklore" fact, which can be viewed as a ... • 4,471 3 votes Accepted ### Recursive generic oracles I think the point is that every notion of genericity has uncountably many generic oracles in it (see, e.g., Fenner-Fortnow-Kurtz-Li Lemma 3.12), but there are only countably many computable sets, so ... • 37.4k 3 votes Accepted ### Given oracle for Max-3SAT compute clauses that cannot be satisfied Given an instance of 3SAT with$m$clauses, you can find the set of clauses that are not satisfied in some optimal assignment with$O(m)$calls to the oracle. The algorithm: Call the oracle on the ... • 164 3 votes ### Ruzzo-Simon-Tompa oracle access mechanism In this paper https://people.cs.rutgers.edu/~allender/papers/pl3.pdf Mitsu Ogihara and I show that the "oracle" #L hierarchy (and related classes) with the Ruzzo-Simon-Tompa access mechanism ... • 2,076 2 votes ### Using an oracle to find a vector$b$for which$Ax=b$has a solution We can make one observation: adaptive access to the oracle doesn't help. You might as well fix in advance the set of queries you plan to make to the oracle. So, the condition is that there has to ... • 12.2k 2 votes ### Compressing information about the halting problem for oracle Turing machines Let$J^A(e)$be the output of the$e$th Turing machine equipped with oracle$A$, on input$e$. Here$J$stands for "jump". (In case of non-halting,$J^A(e)$is undefined.) An oracle$A\$ is jump-...
• 4,485

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