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:
...
- 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 ...
- 8,546
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 :...
- 35.7k
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 ...
- 1,321
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.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 ...
- 18k
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,718
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 ...
- 35.7k
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 ...
- 26.3k
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 ...
- 35.7k
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 '...
- 35.7k
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 (...
- 18k
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 ...
- 1,321
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=...
- 14.8k
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}$ ...
- 35.7k
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 ...
- 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 ...
- 2,828
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 ...
- 35.7k
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 ...
- 1,704
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 ...
- 13.3k
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$.
- 4,400
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 ...
- 14.8k
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)...
- 455
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 ...
- 455
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
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 ...
- 2,237
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 ...
- 35.7k
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,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&...
- 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 ...
- 21
Only top scored, non community-wiki answers of a minimum length are eligible