Skip to main content

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.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
56 views

What different computational powers do I get from an oracle for an undecidable problem?

Suppose that I have got an oracle to some undecidable decision problem, say, for some language $L$. Examples include Halting problem group isomorphism problem whether a Turing machine is a busy ...
shuhalo's user avatar
  • 1,159
3 votes
0 answers
64 views

Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
DiegoEmilio's user avatar
0 votes
1 answer
113 views

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

I have been trying to find an argument, but with no success so far. My understanding is that if I can choose $A$ to be an $EXP-complete$ language, then I can simply reduce any other problem to that ...
Meki21's user avatar
  • 3
8 votes
1 answer
486 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 ...
Gro-Tsen's user avatar
  • 841
2 votes
0 answers
84 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 ...
Habri's user avatar
  • 21
4 votes
0 answers
73 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 ...
John's user avatar
  • 412
9 votes
1 answer
410 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\...
Gro-Tsen's user avatar
  • 841
4 votes
0 answers
135 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*} &\...
eden hartman's user avatar
1 vote
0 answers
51 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 ...
Alexey Uvarov's user avatar
3 votes
0 answers
103 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 ...
Glycerius's user avatar
  • 131
1 vote
0 answers
72 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 ...
l4m2's user avatar
  • 111
3 votes
1 answer
251 views

Relativized world in which P ≠ NP = coNP

Do we know of an oracle relative to which P ≠ NP but NP = coNP?
Noel Arteche's user avatar
3 votes
1 answer
225 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 ...
eden hartman's user avatar
1 vote
0 answers
97 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$? (...
abelard-to-girard's user avatar
6 votes
1 answer
147 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 \...
user3508551's user avatar
  • 1,153
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 ...
En-Jui Kuo's user avatar
7 votes
1 answer
373 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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
193 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, ...
AngryLion's user avatar
  • 173
3 votes
1 answer
103 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. ...
veryinteresting's user avatar
1 vote
0 answers
60 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, ...
Hajaku's user avatar
  • 11
10 votes
1 answer
186 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 ?
GBathie's user avatar
  • 296
0 votes
0 answers
61 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 ...
Abdallah's user avatar
  • 803
2 votes
0 answers
75 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 ...
Abdallah's user avatar
  • 803
6 votes
1 answer
342 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 ...
chxu's user avatar
  • 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?
Turbo's user avatar
  • 13k
2 votes
1 answer
242 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 ...
Hans Schmuber's user avatar
1 vote
0 answers
128 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 ...
AngryLion's user avatar
  • 173
0 votes
0 answers
46 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 ...
Matt.W's user avatar
  • 11
0 votes
2 answers
225 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 ...
Solomon Ucko's user avatar
4 votes
1 answer
266 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?$$
Turbo's user avatar
  • 13k
2 votes
1 answer
193 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 ...
Turbo's user avatar
  • 13k
2 votes
1 answer
160 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))]}$ ...
Turbo's user avatar
  • 13k
7 votes
1 answer
174 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 ...
dkaeae's user avatar
  • 300
7 votes
0 answers
136 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 ...
user avatar
9 votes
1 answer
597 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 ...
Avi Tal's user avatar
  • 1,606
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 ...
Phylliida's user avatar
  • 1,142
2 votes
1 answer
443 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 \{...
Geoffrey Irving's user avatar
1 vote
0 answers
81 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 $...
Erfan Khaniki's user avatar
5 votes
1 answer
201 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\...
Turbo's user avatar
  • 13k
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=\...
Erfan Khaniki's user avatar
2 votes
1 answer
356 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.
Michael's user avatar
  • 57
7 votes
2 answers
203 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.
Mal's user avatar
  • 355
12 votes
1 answer
666 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,...
Will Sawin's user avatar
5 votes
2 answers
246 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 ...
Turbo's user avatar
  • 13k
2 votes
0 answers
151 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 $...
J.Doe's user avatar
  • 478
22 votes
3 answers
9k 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 ...
Will's user avatar
  • 331
8 votes
1 answer
510 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....
Michael Wehar's user avatar
18 votes
1 answer
863 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 ...
Michael Wehar's user avatar
7 votes
1 answer
271 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 ...
Uthsav Chitra's user avatar
8 votes
1 answer
920 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?
user1033363's user avatar