29
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,498
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.7k
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,758
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 ...
- 36.7k
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 ...
- 36.7k
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 ...
- 9,595
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.1k
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 (...
- 18.1k
7
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 ...
- 36.7k
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 ...
- 2,537
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 '...
- 36.7k
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=...
- 16.5k
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}$ ...
- 36.7k
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,878
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,934
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 ...
- 2,537
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 ...
- 9,595
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.5k
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,465
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$....
- 16.5k
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 ...
- 16.5k
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)...
- 568
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,441
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 ...
- 36.7k
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 ...
- 568
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
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 ...
- 11.6k
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,465
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.7k
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