Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
This site is currently in read-only mode; we'll return with full functionality soon. Follow @StackStatus or visit our status blog for more info.

Questions tagged [oracle-machines]

The tag has no usage guidance.

0
votes
0answers
54 views

Can hypercomputation compute the impossible? [closed]

There are things which are illogical/logically impossible (like saying that 2+2=4 and 2+2=5. Without changing anything in the axioms of mathematics or logic, this would be a contradiction and would be ...
1
vote
0answers
19 views

Is there any specific model/theory that proposes that the universe is an oracle machine? [closed]

Is there any specific (and well known/famous) model/theory that proposes that the universe is an oracle machine? Physicist Roger Penrose said his book "The Shadows of the Mind" It would be just as ...
1
vote
0answers
8 views

$NC$ and $FNC$ oracles low for functional and Stockemeyer classes respectively?

We know $P^{NC}=P$ and $FP^{FNC}=FP$ hold. Do $FP^{NC}=FP$ and $P^{FNC}=P$ hold?
3
votes
1answer
37 views

Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak

In Computational Complexity -- A Modern Approach, by Arora and Barak, they have the following claim (Example 3.6). Let EXPCOM be the following language $$ \{ \langle M, x, 1^n\rangle \mid M \text{...
4
votes
3answers
213 views

Oracle machine solving halting problem for other oracle machines

Could someone give me a simple explanation why an oracle machine that can solve the halting problem for standard Turing machines, is however unable to solve the halting problem for other such oracle ...
0
votes
0answers
31 views

Is it true that $NP^{NP}=NP$, or it is true just if there is an assumption that $NP=CO-NP$? [duplicate]

Is it true that $NP^{NP}=NP$, or it is true just if there is an assumption like $NP=CO-NP$? I was proving that $NP^{NP}=NP$ by using the assumption that $NP=CO-NP$ but it seems that it might by ...
1
vote
1answer
36 views

Question on time hierarchy [closed]

How can I prove that $\mathsf{DTIME}^{\mathrm{Htm}}(n^2)$ is contained in $\mathsf{DTIME}^{\mathrm{Htm}}(n^3)$? (sorry about how it is written. I mean the set of languages decided by a deterministic ...
2
votes
1answer
60 views

Is the existence of an oracle such that $P^O = NP^O$ nontrivial?

This famous paper proves the existence of both oracles $A$ and $B$ such that $\textbf{P}^A = \textbf{NP}^A$ and $\textbf{P}^B \neq \textbf{NP}^B$, therefore proving that any resolution to the P versus ...
3
votes
1answer
55 views

Specific example of a problem that shows why **NP** isn't low for itself

Wikipedia says Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. This implies that NP isn't low for itself unless NP =...
0
votes
0answers
13 views

Characterization of P in the context of probabilistically checkable proofs [duplicate]

The PCP theorem characterizes NP as the class of problems checkable probabilistically using log(n) bits and a constant number of random bits and yields $NP=PCP(O(log(n)),O(1))$ . Is there a pair $(f,...
1
vote
1answer
71 views

Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?

Here is a quote from the Source 1: For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the ...
1
vote
0answers
26 views

Oblivious oracle TM's

In "The Complexity Theory Companion" Hemaspaandra and Ogihara define an oblivious oracle TM as an oracle TM where the queries are dependent on the input and not on the oracle. They then show how to ...
2
votes
1answer
44 views

Defining polynomial hierarchy with oracle machines and quantifiers

While trying to understand the concept of polynomial hierarchy, I noticed that there are several ways to define it. And the most confusing thing about the situation is to see the equivalence between ...
1
vote
1answer
32 views

Manipulating Intersection of oracles

Suppose for different classes $A,B,C$ we have that $A\subseteq P^B$ and $A\subseteq P^C$. We have $A\subseteq P^{B}\cap P^{C}$. Does it also mean $A\subseteq P^{B\cap C}$? Supposing $A\subseteq P^{B\...
3
votes
1answer
54 views

Limited oracle TM

Let $M$ be a Turing machine with oracle to $B$ that can decide $B$ in polynomial time. In the general case it means nothing, since we can just pass the input as a query to the oracle of $B$ and accept/...
0
votes
0answers
21 views

On query equally powerful oracles?

If $\mathcal C=\mathcal D$ then does $\mathcal A^\mathcal C=\mathcal A^\mathcal D$ hold ($\mathcal C^A=\mathcal D^A$ need not hold)? The class $\mathcal A$ could query same for $\mathcal C$ and $\...
0
votes
1answer
70 views

On $UP$, $NP$, $\oplus P$ and $PP$?

We know $UP\subseteq NP\subseteq PP$. Is $UP^{\oplus P}\subseteq NP^{\oplus P}\subseteq PP^{\oplus P}$? I think the first $UP^{\oplus P}\subseteq NP^{\oplus P}$ is straightforward since whatever ...
1
vote
1answer
50 views

If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible?

We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $n > N_c$, $$\...
0
votes
0answers
40 views

Is it possible to simulate oracle machines on 1-dimensional cellular automata?

My instinctual response is that it is possible, but I can't see how to simulate the oracle tape on a 1-d CA. If not, are they able to be simulated on n-dimensional CA? My thought is that the oracle ...
1
vote
1answer
229 views

Is the set of languages recognized by a Turing machine with an oracle countable?

I am currently taking a class in complexity theory and I am struggling with this question. We define a TM with Oracle per. Sipser 6.18 as: "An oracle for language $B$ is an external device that is ...
2
votes
1answer
197 views

A question on oracle turing machines

I am trying to solve a question from the exercise of this book, pg. 46,section 7.4. Let $M$ be a deterministic Turing machine that only queries oracle strings that are shorter than the input string. ...
2
votes
2answers
216 views

What is the relationship between oracle Turing machine $M^O$ and Turing machine $M$ (given $O$)?

An oracle Turing machine (OTM) $\bar{M}$ can be denoted $M^{O}$ if it is a Turing machine (TM) $M$ with an oracle $O$. Given the oracle $O$, there exists a relation $R$ between OTMs and TMs such that $...
1
vote
1answer
297 views

How to calculate Kolmogorov Complexity if we have access to an Oracle for the HALT Problem

I try to solve the following exercise: We know that K (x), the complexity of Kolmogorov, is incomputable. Show how calculate it, if we have an oracle for the membership problem (or for the HALT ...
3
votes
1answer
225 views

Oracle Turing Machine $EXP^{EXP}$

I'm reading Arora Barak and in that it is written that when $O \in P$, then $P^O = P$. Can this be generalized? Intuitively, I think that $NP^{NP} \neq NP$ but $EXP^{EXP} = EXP$ Am I right? Any ...
2
votes
1answer
56 views

If we allow a database, what complexity class it is?

Let we have some problem $A$. Input length is $n$. Now we write a database that will store info about some positive instances of problem $A$. For every $n$ size of $n^{th}$ sector of DB is $O(f(n))$. $...
-1
votes
1answer
113 views

Check if $P^{NP} = P^{coNP}$

Check if $P^{NP} = P^{coNP}$ To my eye answer is "unknown". I would try to show that it implies that $coNP=NP$, what is unknown fact. Lets suppose that $P^{NP} = P^{coNP}$. Then we use simply ...
2
votes
1answer
75 views

What is the relation of complexity class $L^L$ to other complexity classes?

What is the relation of complexity class $L^L$ to other complexity classes? (Here $L^L$ is the complexity class of decision problems solvable by a TM in logspace with an oracle for a language in ...
2
votes
1answer
37 views

$UP^{\ O}\neq P^{\ O}$ for some oracle $O$

The definition of the class $UP$ is here. It is of course easy to see that $P\subseteq UP$. I have a problem of proving that there is an oracle $O$ and a language $L$ such that $L\in UP^{\ O}$ but $...
0
votes
0answers
57 views

Showing if $A\in DSPACE(n^c) \text{ or } DTIME(n^c)$ then $EXP^A \neq EXP$ and $EXP^A= EXP$

If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$ If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$ What I tried: Since it's impossible to show that $EXP \subseteq EXP^A$ because: We ...
1
vote
1answer
117 views

What does it mean for a problem to be solved in polynomial time “relative to” an oracle?

I came across the following theorem in page 12 of the following pdf : There exists an oracle relative to which there is a problem solvable in polynomial time (with bounded error probability) on a ...
2
votes
1answer
78 views

Are all proof techniques which only look at black box behaviour of a TM relativizing?

I am currently working on a seminar on $\mathbf{P \stackrel{?}{=} NP}$ and one of the points I want to adress is the Relativization barrier. However, it is hard to find a concrete definition of a "...
5
votes
1answer
254 views

What is an approximation oracle?

I have seen the term "approximation oracle" in computer science papers, sometimes parameterized with the letters $\alpha$ and $\beta$. What is an approximation oracle? How are such oracles used? I am ...
1
vote
0answers
63 views

Question about $\mathsf{Almost–PSPACE}$

A language is in $\mathsf{Almost\text{-}PSPACE}$ if there is a (deterministic) $\mathsf{PSPACE}$ Turing machine with an oracle $A$ that accepts the language with probability $1$ when the ...
1
vote
0answers
62 views

On oracle access containment?

If $X,Y$ are complexity classes in the polynomial hierarchy with $X\subseteq Y$. With abuse of notation assume $X,Y$ also as the TMs that accept languages in classes $X,Y$ respectively. Then is it ...
3
votes
1answer
659 views

Why can't we simulate an NP oracle with an NP machine?

In this question : Does $NP^{NP}=NP$? , it says that one of the reason is that we don't know how to detect 'no' answers from the oracle. Why is that true though? There is an NTM for any language L in ...
3
votes
1answer
146 views

Existence of suitable pseudo-random number generators to derandomize BPP to P

I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other. My understanding is that if there is a suitably strong ...
3
votes
1answer
157 views

Precise definition of oracle classes $A^B$

I was reading in Papadimitriou's "Computational Complexity" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a ...
2
votes
1answer
167 views

If a language is not Turing reducible to two languages, may it still be Turing reducible to their “union”?

Consider a language $L$ that is undecidable relative to $L_1$ and is also undecidable relative to $L_2$. Suppose, however, that there is a "multi"-oracle Turing machine $M$ that can query both the $...
4
votes
1answer
745 views

Proving that the halting problem is not Turing-reducible to the acceptance problem for Turing machines

Consider $\mbox{Halt}_\mbox{TM} = \{\langle M, w \rangle: M \mbox{ is a TM and } M \mbox{ halts on input } w\}$ and $\mbox{A}_\mbox{TM} = \{\langle M, w \rangle: M \mbox{ is a TM and } M \mbox{ ...
3
votes
1answer
385 views

Can a Turing machine be both decidable and undecidable relative to itself?

Consider the language: $A'_{TM} = \{\langle M,w\rangle: M \mbox{ is a TM with access to an oracle for } A_{TM} \mbox{ and } M \mbox{ accepts } w\}$ Clearly, we expect that any language is decidable ...
1
vote
0answers
157 views

Turing machine with an oracle for a proper subset of a known undecidable language

Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $...
1
vote
0answers
168 views

Misunderstanding the Baker-Gill-Solovay oracle and obtaining $LOGSPACE^A=PSPACE^A$

Baker, Gill and Solovay [1] gave an oracle $A$ relative to which $P^A=PSPACE^A$. The oracle is the very simple $PSPACE^A$-Complete language $$A = \{\langle M, x, 1^n \rangle | M^A \text{ accepts } x \...
1
vote
2answers
78 views

Superscript on complexity class?

What does it mean when one complexity class has another complexity class superscript? For example, sometimes in papers I see $P^P$ or $P^{NP}$.
1
vote
1answer
53 views

Is this language in $PSPACE^{L'}$?

Let's assume we have an arbitrary language $L'$ and let's define the language $L = \{1^n | \text{The number of strings in } L' \text{ of length } n \text{ is odd }\}$. Is $L\in PSPACE^{L'}$? I tried ...
5
votes
2answers
123 views

Countably many oracle Turing machines?

In Sipser's text, when proving that there exists an oracle $A$ such that $P^A \ne NP^A$, he writes: Let $M_1, M_2, \ldots$ be a list of all polynomial time oracle TMs. I understand that there are ...
0
votes
0answers
36 views

Oracle machine and boolean formula

Let we have oracle machine. Oracle get boolean formula and answer OK if this formula is feasible. How to explain that we can find satisfying assignment for any formula for polynomial time. I have аn ...
3
votes
1answer
84 views

Complexity Theory - Why can't you use diagonalization to seperate classes A and B when an orcale O exists under which A=B?

In a recent lecture the professor stated that given two complexity classes A and B, and given the existance of an oracle O such that $$A^o=B^o$$ (As I understand, meaning that a problem in A with can ...
5
votes
1answer
65 views

Questions about class of problems that can be solved with unlimited computational power, but access to only logarithmically many bits of the input?

Consider the class $\text{DLOGTIME}^{\text{ALL}}$: the class of problems that can be solved by a machine with unlimited computational power but only access to logarithmically many bits of the input. ...
1
vote
0answers
67 views

Would a 'smallish' oracle for an NP complete problem actually be useful?

A quick thought experiment here: Suppose one could construct an oracle that could yield a solution to an NP-complete problem (3SAT, TSP, SUBSET, etc) for smallish (30-60) inputs in a single operation....
0
votes
0answers
18 views

Is NP-complete complexity defined in terms of polynomial reductions or polynomial transformations? [duplicate]

How do you know that a decision problem $X$ is NP-complete?, if all other NP-problems polynomially transform to $X$ or if all other NP-problems polynomially reduces (there exist a polynomial time ...