Skip to main content
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: ...
Craig Gidney's user avatar
  • 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 ...
cody's user avatar
  • 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 ...
Mikhail Rudoy's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
Neal Young's user avatar
  • 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 ...
Ryan Williams's user avatar
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 ...
Joshua Grochow's user avatar
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. ...
Emil Jeřábek's user avatar
7 votes

Oracle comparing $EXP$ with $UP$

The quoted Beigel, Buhrman, and Fortnow paper gives a solution to 2 in Theorem 1.8: there is an oracle relative to which $\mathrm{P=Mod_3P}$ (which implies $\mathrm{P=UP}$), and $\mathrm{\oplus P=NP=...
Emil Jeřábek's user avatar
7 votes
Accepted

Oracle comparing $EXP$ with $UP$

$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ ...
Joshua Grochow's user avatar
7 votes
Accepted

Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (...
Sasho Nikolov's user avatar
7 votes
Accepted

How to prove $P^{Halt} = PSPACE^{Halt}$

Using $n$ calls to the halting oracle and time $O(n^2)$, you can compute the first $n$ bits of the Chaitin's constant. Using the $n$ bits of the Chaitin's constant and unbounded time, all queries to ...
Dmytro Taranovsky's user avatar
7 votes
Accepted

What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

$\mathsf{MA_{EXP}} \not\subseteq \mathsf{P/poly}$ but there is an oracle relative to which this is false; both were proved in H. Buhrman, L. Fortnow, T. Thierauf. Nonrelativizing separations. CCC '...
Joshua Grochow's user avatar
6 votes

Results comparing BQP and NEXP

The oracle you ask for has $P=NP\ne BQP=NEXP$, and therefore it has $BQP\ne PH$. Finding any oracle relative to which $BQP\ne PH$ was an open problem for twenty years until Raz and Tal [1] found such ...
Lieuwe Vinkhuijzen's user avatar
6 votes
Accepted

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

On popular request, here is my comment as an answer: There is an oracle separating $\mathrm{PP}$ from $\mathrm{PSPACE}$: Jacobo Toran, A combinatorial technique for separating counting complexity ...
Markus Bläser's user avatar
6 votes
Accepted

Is P=NP relative to the halting oracle?

$\text{P}^\mathcal{H} = \text{NP}^\mathcal{H} = \text{PSPACE}^\mathcal{H}$ as noted in the linked answer (note that the query tape counts as space). Specifically, using $n$ calls to the halting ...
Dmytro Taranovsky's user avatar
5 votes
Accepted

Oracle-Decidability of Algebraic Independence

The answer is no; interestingly, the problem is harder to state satisfactorily in my opinion than it is to resolve! Roughly speaking, the subtlety which complicates the posing of the problem is that ...
Noah Schweber's user avatar
5 votes
Accepted

Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$

Theorem 1. For any $\epsilon>0$, there is a $(1+\epsilon)$-approximation algorithm that makes $O(\epsilon^{-1}\log n)$ queries. Note that if $\epsilon$ is arbitrarily small but constant, the ...
Neal Young's user avatar
  • 10.8k
5 votes

Lower bound on alternations needed in $BQP$ versus $PH$ result?

If you just want oracle separations with $\#P$, you don't need to use the new result of Raz and Tal. You can use the classic Parity/Majority not in $AC^0$ results from the 1980s. For example, the ...
Robin Kothari's user avatar
5 votes

P vs. NP in a logic with a random oracle

Yes on Question 1 (assuming ZFC is consistent). You don't need $f$ to be random exactly, any $f$ will do. And for the proof you need to also use the fact that there is an oracle $h$ with NP$^h=$P$^h$.
Bjørn Kjos-Hanssen's user avatar
5 votes
Accepted

Relativized world in which P ≠ NP = coNP

Some oracles of this sort were given in other answers on this site: https://cstheory.stackexchange.com/a/1545 gives references to an oracle $A$ such that $\mathrm{EXP}^A=\mathrm{NP}^A=\mathrm{ZPP}^A$....
Emil Jeřábek's user avatar
5 votes
Accepted

Why does there not exist an oracle $A$ such that $EXP^{A} = P^{A}$?

The known separation $\mathbf{P} \neq \mathbf{EXP}$ is a relativizing result, meaning that it works even in the presence of oracles i.e., it holds that for every oracle $O$, $\mathbf{P}^O \neq \mathbf{...
Noel Arteche's user avatar
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 ...
Emil Jeřábek's user avatar
4 votes
Accepted

Turing meta-oracle

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)...
Noah Schweber's user avatar
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 ...
Clement C.'s user avatar
  • 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 ...
Joshua Grochow's user avatar
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 ...
Tom Tseng's user avatar
  • 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 ...
Eric Allender's user avatar
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 ...
D.W.'s user avatar
  • 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-...
Bjørn Kjos-Hanssen's user avatar

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