Hot answers tagged

27 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: ...
user avatar
  • 1,458
26 votes
Accepted

Is there an oracle such that SAT is not infinitely often in sub-exponential time?

You can just take the oracle A s.t. NP$^A$=EXP$^A$ since EXP is not in i.o.-subexp. For SAT$^A$ it depends on the encoding, for example if the only valid SAT instances have even length then it is easy ...
user avatar
17 votes
Accepted

For a random oracle R, does BPP equal the set of computable languages in P^R?

Yes. First, since it took me a minute to figure this out myself, let me formalize the difference between your question and $\mathsf{AlmostP}$; it's the order of quantifiers. $\mathsf{AlmostP} := \{L :...
user avatar
16 votes

Is there an oracle such that SAT is not infinitely often in sub-exponential time?

You don't have to go to the lengths Lance was suggesting. For example, relative to a random oracle, using the oracle as a one-way function (say, evaluated on consecutive bit postions) is ...
user avatar
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 ...
user avatar
  • 13.2k
11 votes

Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

This version of the answer incorporates feedback from Emil Jeřábek. As far as I can see, the main twist is that there is a language in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ of exponential circuit ...
user avatar
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 ...
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 ...
user avatar
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 ...
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 ...
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 '...
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 (...
user avatar
7 votes

For a random oracle R, does BPP equal the set of computable languages in P^R?

While the order of quantifiers between what you are asking and almost P differ, it is not too hard to show that they are equivalent. First, for any fixed L, the question of whether L \in P^O does ...
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=...
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}$ ...
user avatar
7 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 ...
user avatar
  • 8,143
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 ...
user avatar
6 votes
Accepted

Lower bounds for nonuniform circuits and oracles separating complexity classes

Yes, yes, and yes. The basic idea is to consider the characteristic function of a language $L$ (the oracle you're constructing) at length $n$ as a string of length $2^n$ that will be an input to a ...
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 ...
user avatar
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 ...
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$.
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 ...
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)...
user avatar
3 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 ...
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 ...
user avatar
  • 164
3 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 ...
user avatar
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 ...
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 ...
user avatar
  • 4,341
2 votes

Possibility of hierarchy with $UP$ class?

Problem 2. answered in references a. https://arxiv.org/pdf/cs/9907033.pdf b. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=19DD617ABDB31709CA0BEF797C283867?doi=10.1.1.60.9357&rep=rep1&...
user avatar
  • 12.5k
2 votes

Partitioning a square for optimal queries

A good idea seems to be to use nonoverlapping circles in the densest circle packing in 2d. Please check the corresponding Wiki-page: https://en.wikipedia.org/wiki/Circle_packing. This way you reach up ...
user avatar

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