Questions tagged [oracles]
Questions regarding oracle machines in computational complexity theory. Oracles can serve as an indicator that a separation between complexity classes is beyond the scope of certain proof techniques.
105
questions
8
votes
1
answer
414
views
What can we do with a generic oracle (as opposed to a random one)?
Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question):
Standard definitions: A ...
- 619
1
vote
0
answers
65
views
Crafting ${NP}^{\#P}$-complete problems
Some related posts:
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$
I needed a complete problem for the class ${NP}^{\#P}$ for a reduction to show the hardness of some other ...
- 11
4
votes
0
answers
70
views
distinguishments between query complexity of membership oracles and standard time complexity
Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to ...
- 173
9
votes
1
answer
328
views
Is P=NP relative to the halting oracle?
Consider the following variant $\mathscr{H}$ of the halting oracle: given the code $e$ for an ordinary Turing machine and an input $n$ to it, we let $\mathscr{H}(\langle e,n\rangle) = \langle 0,0\...
- 619
4
votes
0
answers
132
views
Which variant of the ellipsoid method was used for the Santa Claus problem?
As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual):
\begin{align*}
&\...
- 91
1
vote
0
answers
48
views
Oracle for the permanent-of-gaussians problem
In this paper, Aaronson and Arkhipov formulate the $GPE_\times$ problem as follows: given an $n \times n$ matrix $X$ of i.i.d. Gaussian random numbers, find the permanent of $X$ up to multiplicative ...
- 111
3
votes
0
answers
99
views
$\mathsf{coNP}^{\mathsf{\#P}}$ and $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$
I was reading a paper that demonstrates that deciding whether a loop-free program is $\varepsilon$-differentially private is $\mathsf{coNP}^{\mathsf{\#P}}$-complete. What are some other problems that ...
- 131
1
vote
0
answers
69
views
Is NLOGTIME self-low?
https://en.wikipedia.org/wiki/Low_(complexity)
Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. EXP, which is closed ...
- 111
3
votes
1
answer
248
views
Relativized world in which P ≠ NP = coNP
Do we know of an oracle relative to which P ≠ NP but NP = coNP?
- 871
3
votes
1
answer
210
views
Can the ellipsoid method be used with a randomized separation oracle?
Suppose we are trying to solve the following optimization problem:
$$
\text{maximize } ~~ c\cdot y
\\
\text{subject to } ~~ y\in S
$$
where the region $S$ is described by an exponential number of ...
- 91
1
vote
0
answers
89
views
Is complexity class containment preserved relative to any oracle?
That is, suppose $A\subseteq B$ for two complexity classes $A$ and $B$. Is it the case that for any oracle $C$, and any definitions $A^*$ and $B^*$ of $A$ and $B$, we have ${A^*}^C\subseteq {B^*}^C$? (...
6
votes
1
answer
139
views
Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$
This is a cross-post from a question I asked on cs.stackexchange 2 weeks ago with no answers. I thought it might find home here.
We are given sorted $0\leq x_1 \leq x_2 \leq \dots \leq x_n$ and $y_1 \...
- 1,088
0
votes
1
answer
65
views
Power of unique counting class
One question that recently encountered is the following, suppose I have a task $L$ which has input length $n$, the problem is in the $\text{NP}$ and I promise that there is a unique solution. (The ...
6
votes
1
answer
351
views
Is there a simplex-like algorithm that can be used with a separation oracle?
Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the smoothed analysis framework of Spielman and Teng ...
- 2,078
1
vote
1
answer
186
views
Young Diagrams and distinguishing between two distributions
Introduction:
The reference for everything is this paper.
The Robinson–Schensted–Knuth (RSK) algorithm is a well-known
combinatorial algorithm with diverse applications throughout
mathematics, ...
- 173
3
votes
1
answer
99
views
Recursive generic oracles
In
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide, An oracle builder’s toolkit, Inf. Comput. 182, No. 2, 95-136 (2003). ZBL1025.68041, the authors go through a variety of generic oracles.
...
1
vote
0
answers
58
views
Does a decision oracle imply an algorithm for $\mathbb{NP}$ - hard problems with several parameters?
If we consider the decision version of the classical graph coloring problem, then we have some graph $G$ and some integer $k$ and we want to color $G$ with at most $k$ colors. It is well known that, ...
- 11
10
votes
1
answer
182
views
It is known that $L \subsetneq PH$?
Is it known whether $Logspace$ is strictly contained in the polynomial time hierarchy ?
Are there oracles relative to which these classes are equal / distinct ?
- 296
0
votes
0
answers
60
views
Is anything known about NC$^1$ with NP oracle
A few things are known about the class $\textsf{L}$ provided with an $\textsf{NP}$ oracle ($\textsf{L}^\textsf{NP} = \Theta_2^\textsf{P}$ has attracted a bit of attention, for instance [1]) On the ...
- 803
2
votes
0
answers
72
views
Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies
If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class $\textsf{P}^{\textsf{NP}[\log]}$, also known as $\Theta_2^{\textsf{P}}$, sits at the top of the ...
- 803
6
votes
1
answer
339
views
Are all problems in the same time hierarchy related to each other?
In this problem, "runtimes" refer to worst-case complexity compared up to constant factor.
Say you have two problems, A and B, in the same time hierarchy, and it is clear that algorithm P ...
- 69
1
vote
0
answers
138
views
Is there an oracle that separates $PH$ from counting classes?
Is there an oracle $A$ for which $P^A =PH^A \neq CH^A = NEXP^A$ holds?
- 12.8k
2
votes
1
answer
237
views
Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?
Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$.
For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic ...
- 383
1
vote
0
answers
124
views
Oracle separation between coNP and QMA implies oracle separation between NP and QMA
In [this] paper, Aaronson remarks (page 2, footnote) that:
From the BBBV lower bound for quantum search [6], one immediately
obtains an oracle $A$ such that $coNP^{A} \not\subseteq QMA^{A}$ for ...
- 173
0
votes
0
answers
45
views
What is the meaning of an Oracle in data clustering?
I am not sure whether this is the best place to ask this question. I am in the process of researching the area in data clustering as well as the algorithms that are associated with it and the term ...
- 11
-1
votes
2
answers
218
views
Turing meta-oracle
Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
- 109
4
votes
1
answer
260
views
Results comparing BQP and NEXP
Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$
Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$
- 12.8k
2
votes
1
answer
190
views
Possibility of hierarchy with $UP$ class?
I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
- 12.8k
2
votes
1
answer
152
views
Lower bound on alternations needed in $BQP$ versus $PH$ result?
What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
- 12.8k
7
votes
1
answer
171
views
Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?
While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around:
Note that the general ...
- 300
7
votes
0
answers
133
views
Can relativization technique be applied to natural NP-complete languages?
Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
user17918
9
votes
1
answer
576
views
Indications that strengthen the conjecture: NEXP ⊊ EXP^NP
I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP.
Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper.
Some Examples:
1. A paper by Shuichi ...
- 1,596
0
votes
2
answers
96
views
Partitioning a square for optimal queries
I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles:
$f(x, y, r)$ tells me how many ...
- 1,132
2
votes
1
answer
430
views
P vs. NP in a logic with a random oracle
Choose a random oracle $f : \{0,1\}^\ast \to \{0,1\}$, and define the logic $ZFC^f$ by adding a fresh symbol $g$, an axiom that $g$ has the correct type, and one axiom $g(s) = f(s)$ for each $s \in \{...
- 3,243
1
vote
0
answers
79
views
Kolmogorov generic oracle
In Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?, authors defined a new type of generic oracles named Kolmogorov generic oracles.
They proved following results relative to $...
- 332
5
votes
1
answer
193
views
Is $UP\not=NP$ with respect to random oracle?
It is shown in An average-case depth hierarchy theorem for Boolean circuits a random oracle makes $PH$ infinite.
Is it possible to also show $UP\not=NP\not=\Sigma_2^P\not=\Sigma_3^P\not=\Sigma_4^P\...
- 12.8k
1
vote
0
answers
86
views
On collapsing the Exponential time hierarchy
Define $\Sigma^E_0 = \Pi^E_0=E$,
for every $n>0$, define $\Sigma^E_n=NE^{\Sigma^p_{n-1}}$,
for every $n>0$, define $\Pi^E_n=CoNE^{\Sigma^p_{n-1}}$.
Define the Exponential time hierarchy by $EH=\...
- 332
2
votes
1
answer
314
views
How to prove $P^{Halt} = PSPACE^{Halt}$ [closed]
Halt means the halting set. $PSPACE^{Halt}$ is the class of problems that can be solved with polynomial memory (possibly exponential time), given a halting oracle.
- 57
7
votes
2
answers
197
views
What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?
In this article Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$.
I wanted to know if there are more examples like this.
- 355
12
votes
1
answer
644
views
Compressing information about the halting problem for oracle Turing machines
The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable.
More precisely,...
- 221
5
votes
2
answers
245
views
Oracle comparing $EXP$ with $UP$
Heller (Theorem 6) gave an oracle relative to which $NP=EXP$, and Homer & Selman gave an oracle relative to which $P=UP$ and $\Sigma_2^P=EXP$.
Beigel, Buhrman, Fortnow (freely available author's ...
- 12.8k
2
votes
0
answers
148
views
Complexity of $FP^{NP[O(n)]}$ with advice string?
$FP^{NP[O(n)]}$ is the functional complexity class with $O(n)$ queries to an $NP$ oracle.
Are there any interesting classes $\mathcal C$ such that
$$FP^{NP[O(n)]}\subseteq\mathcal C/\log$$
besides $...
- 468
22
votes
3
answers
8k
views
Oracle Construction for Grover's Algorithm
In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...
- 331
8
votes
1
answer
475
views
Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?
Background
We know that $P^{\#P} \subseteq PSPACE$.
In addition, we known from
Toda's theorem that $PH \subseteq P^{\#P}$.
For more background on $\#P$, see here:
https://en.wikipedia....
- 5,127
18
votes
1
answer
840
views
What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?
Background
It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$.
It is even known that the separation holds relative to a random
oracle. Informally, one may interpret ...
- 5,127
7
votes
1
answer
268
views
Using an oracle to find a vector $b$ for which $Ax=b$ has a solution
There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$. The oracle takes as input an integer vector $b$ with positive entries, and answers as ...
- 233
8
votes
1
answer
892
views
Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?
If it is unknown, are there reasons to believe that they might not be equal?
- 137
7
votes
0
answers
187
views
SETH-like hypothesis for machine with oracle access to some level of PH
I am wondering if hypothesis such as Strong Exponential Time Hypothesis (SETH) have been studied for problems being in a higher level of the polynomial hierarchy when we give the machine access to an ...
- 2,164
3
votes
0
answers
456
views
Oracle separating $coNP$ and $NP/poly$
I'd like to prove that, with respect to some adversarial oracle $O$, $coNP^O \not\subseteq NP/poly^O$. I was thinking of using $\textsf{UNSAT}$ for this and to build my oracle as follows: $O$ will "...
- 137
7
votes
0
answers
202
views
Oracles for sub-exponential circuit complexity of $\Sigma_2 EXP$
Couldn't find this one anywhere...
It's an open problem whether $\Sigma_2 EXP$ problems have exponential-size circuit complexity. Is there an oracle relative to which $\Sigma_2 EXP$ has $2^{o(n)}$ ...
- 27.3k