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

Questions tagged [oracle-machines]

The tag has no usage guidance.

2
votes
1answer
45 views

Show that the following language is undecidable

$\{ M \mid M \text{ is a machine that runs in }100n^3 + 300\text{ time }\}$ I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first ...
3
votes
1answer
38 views

The power of relativised proofs

I've been trying to understand why, for instance, even though there are oracles $A$ for which $P^A \neq NP^A$, we still don't know if $P=NP$. As I understand it, it's because it's easy to construct ...
3
votes
1answer
44 views

Complexity class for NP with access to a DP oracle

Consider the following decision problem: Given: Two (3CNF-)formulas $\varphi_1$, $\varphi_2$ on a shared set $X\cup Y$ of variables ($X$ and $Y$ disjoint). Question: $\exists$ assignment $\...
2
votes
1answer
73 views

Why is Graph Isomorphism downward self reducible?

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing ...
1
vote
0answers
21 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
40 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
269 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
34 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
40 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
63 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
57 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
74 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
29 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
46 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
55 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
41 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
240 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
202 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
241 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
335 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
248 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
58 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
121 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
78 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
59 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
121 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
82 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
263 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
64 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
66 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
690 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 ...
2
votes
1answer
149 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
171 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
174 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
806 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
396 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
168 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
180 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
81 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
54 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
124 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
37 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 ...
2
votes
1answer
85 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 ...