Questions tagged [oracle-machines]
The oracle-machines tag has no usage guidance.
140
questions
3
votes
1
answer
66
views
Does $A^B = A^C$ imply $B = C$?
I am familiar with the Baker, Solovay, Gill result of non-relativization of P vs NP problem. They showed that $\exists A \text{ s.t }P^A \neq NP^A$. But since we are referring to $P, NP$ as models of ...
- 243
0
votes
1
answer
13
views
Transform OTM for Problem π to DTM ∈ DSPACE(n)
Given an Oracle Turing machine ($OTM$) that solves Problem π in max. 2n space, so $O(n)$ space and $O(n^2)$ time.
Is there a DTM that can solve $π$ in $O(n)$ space if time doesn't matter? (The length ...
- 11
1
vote
0
answers
40
views
Is $\mathsf P$ low for every complexity class between itself and $\mathsf{NP}$?
We know that $\mathsf P$ is low for itself. It's also low for $\mathsf{NP}$, $\mathsf{RP}$, $\mathsf{UP}$ and some other complexity classes that contain $\mathsf P$ and are contained in $\mathsf{NP}$. ...
- 1,632
1
vote
1
answer
44
views
Showing SAT is auto-reducible
I am trying to wrap my head around the concepts of auto-reducibility and having access to an Oracle.
The way I understand is that a language is auto-reducible iff there is a Turing Machine $M^{L}(x)=1$...
- 93
0
votes
1
answer
29
views
A machine with multiple oracles
Suppose a machine $T$, and oracles $A$ and $B$ solve all problems in the complexity classes $\mathcal C_T$, $\mathcal C_A$ and $\mathcal C_B$ respectively.
Let $T^{\{A,B\}}$ denote a machine that is ...
- 1,632
1
vote
0
answers
36
views
$FINITE_{TM}$ is not Turing-reducible to $A_{MT}$
$FINITE_{TM} = \{\langle M \rangle\mid M\text{ is a TM and }L(M)\text{ is finite}\}$
$A_{MT} = \{\langle M,w \rangle \mid M\text{ is a TM and }M\text{ accepts }w\}$
I'm trying to prove that $FINITE_{...
0
votes
1
answer
25
views
P/poly and dyadic oracle
If we let a language L in {0,1}* be dyadic if for each x in L, and each index i with xi = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with ...
- 23
0
votes
0
answers
20
views
Relativizations/Oracles for the BPP and RP complexity classes
If we consider the complexity classes RP and BPP, then to show RPBPP = BPPRP my first thought is we need to use some kind of majority voting to amplify our success probabilities. The issue is I don't ...
- 23
0
votes
0
answers
18
views
Analogue of NP for oracle problems
I was just reading this question on the quantum computation stack exchange. It asks whether the HSP is in NP or not, and the answer notes that NP is a class of languages, not oracle problems.
The ...
- 327
1
vote
1
answer
53
views
Does $\texttt{Oracle-SAT} \leq_T^P \texttt{SAT} \iff \texttt{P} \neq \texttt{NP}$, and is this possible?
The problem of Oracle-SAT is given below:
Given oracle query access to some machine, $U$ that has $2^N$ inputs, determine if there is an input such that the machine accepts.
This is very similar to ...
- 243
0
votes
0
answers
37
views
Is Quantum Search (SAT with only oracle access) NP-hard (and not NP-complete)?
Quantum search differs from the standard boolean SAT as it is restricted to only oracle calls to a circuit (or CNF formula). Where SAT gives us the structure of a formula (however loosely defined that ...
- 243
2
votes
1
answer
52
views
is $IP=BPP^{NP}$
In the class $IP$ we have a probabilistic polytime verifier which interacts with a nondeterministic prover polynomial times and all the messages are of length polynomial of the input. We can think of ...
- 133
1
vote
1
answer
42
views
Making statements about quantum complexity theory
It is my understanding, based on this question that problems solved on quantum computers with oracles don’t make any statements about BQP in relation to other complexity classes.
The fallacy is in ...
- 11
11
votes
3
answers
3k
views
Detecting if three Turing Machines halt given a magic oracle that is only used twice
We were given a question in class as follows:
You have a "magic oracle" that can decide if a Turing Machine halts. You have three TMs $T_1, T_2, T_3$. Device an algorithm that decides which ...
- 121
1
vote
1
answer
43
views
What Complexity Class Contains $QSAT_{\log n}$?
It is known that $QSAT$ is $PSPACE$ complete, and it is known that $QSAT_i$ is $\Sigma_i$ complete for any constant $i$. However, what if we had $QSAT_{\log n}$? That is, $QSAT$ where the quantifiers ...
- 232
0
votes
1
answer
61
views
Using hypercomputation for "impossible" problems?
In mathematics and philosophy there are some unsolvable problems like Russell's paradox or the liar's paradox that are usually said to be undecidable... There are also other "impossibilities"...
- 101
0
votes
0
answers
64
views
Why isn't $P^A = A$?
I have a question regarding oracles.
If I have the complexity class $P^A$ (with $P \subseteq A$), what is it's relationship to the class $A$?
I mean it should be trivial that $A \subseteq P^A$ for all ...
- 119
1
vote
0
answers
33
views
Why results based on padding generally fail to relativize?
I have read in the Algebrization paper that, if we only allow polynomially-long queries to oracles, then, results based on padding will not relativize. For instance: assuming that $A$ is a PSPACE-...
- 427
1
vote
1
answer
98
views
How can EXP^P be characterized?
I had a question about EXP^P (EXPTIME with access to a P oracle). I thought I had read somewhere that EXP = EXP^P, and that seemed fairly intuitive to me: I thought "adding polynomial power to ...
- 145
0
votes
1
answer
46
views
Could you solve co-RE problems with a halting oracle?
The halting problem is $RE$ complete. With an oracle for the halting problem could you decide problems in $co RE$ with an oracle for RE?
- 229
0
votes
1
answer
47
views
If the time hierarchy theorem holds relative to every oracle, what about a halting(RE) oracle?
I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) ...
- 229
0
votes
0
answers
17
views
Do time-constructible functions exist in relativized worlds?
I know that time-constructible functions are necessary to prove the Time Hierarchy Theorem and being computable functions they are computed by Turing Machines. I'm just confused in that since the Time ...
- 1,621
2
votes
1
answer
68
views
Number of queries for $NP^{NP}$
So a few days ago my lecturer told us that for every nondeterministic polynomial time oracle
machine $M$, there is a nondeterministic polynomial time oracle machine $N$ that gives us $L(N^{3-SAT}) = L(...
- 121
1
vote
1
answer
160
views
What are the differences between Oracle Turing Machine and PAC?
I am having difficulty understanding the difference between PAC and Oracle Machines. I cannot compare these two in terms of uncertainty and physical effort.
The degree of uncertainty we can tolerate ...
- 11
1
vote
4
answers
78
views
Can quantum computers be modelled as a classical computer with access to an oracle?
Quantum computers can solve certain problems faster than classical computers e.g factoring numbers.
and this is because quantum computers can do a fourier transform on $n$ qubits in $O(n^2)$ time as ...
- 91
1
vote
1
answer
148
views
Show that both set A and set B are Turing reducible to some mixture of A and B
Consider an operator $+$ defined on $P(N)$ as follows: $A + B = \{2x\mid x \in A\}\cup \{2x + 1\mid x \in B\}$.
Show that both $A$ and $B$ are Turing-reducible to $A+B$
I am kind of confused about ...
- 59
0
votes
1
answer
134
views
Show that LOOP is reducible to Complement of Halting problem
LOOP = {<M,w1,w2,w3>: M is a Turing machine that doesn't halt on at least 2 of the wi}
HPC = {<M,w> : M is a Turing machine that doesn't halt on w}
Show that LOOP is polynomial time ...
- 59
2
votes
0
answers
181
views
Is there a linear sorting algorithm given an oracle that finds kth smallest item?
Given a machine that can compute the kth smallest item of an Array A in $O(\sqrt n)$ time. Find a recursive function that can sort A in linear time corresponding to $n$ which is the length of A.
First ...
- 143
2
votes
2
answers
347
views
how does Kleene-Post show two languages that are not Turing reducible to each other?
I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument.
I've seen ...
- 858
0
votes
1
answer
155
views
If $PSPACE^{SAT}=PSPACE$ and $PSPACE \subseteq EXP$, then why does $EXP^{SAT}$ not necessarily equal to $EXP$?
I read the following claim:
$PSPACE^{SAT}=PSPACE$
$EXP^{SAT}$ is not necessarily the same as $EXP$
The first claim makes sense; $PSPACE \subseteq PSPACE^{SAT}$ trivially, and for any language $B \in ...
- 31
2
votes
1
answer
161
views
What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to
What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to?
I suspect that their, NEXP, ESPACE and 2EXPtime respecitvely.
And what bout $NP^{EXP}$
- 356
2
votes
1
answer
306
views
Combining 2 problems in NP into one
Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$.
Can S be solved with oracle access to only one problem in $NP$?
...
- 51
2
votes
1
answer
225
views
How to tell if a proof relativizes?
If I have a proof for a separation between two complexity classes (using no oracles) and I want to see if it relativizes, how do I go about doing so?
Especially in the case where there already exist ...
- 345
5
votes
1
answer
400
views
Under what kind of oracles are $P$ and $NP$ equivalent?
How strong have the oracles needed to be for these two classes to be proven equivalent with respect to them?
For instance: is $P^H$ = $NP^H$ (ie. is $P$ equipped with an oracle to solve the halting ...
- 345
2
votes
3
answers
227
views
Are any two complexity classes equipped with an oracle to solve the halting problem equivalent?
Equip any complexity classes $C$ and $B$ (to be more specific: any complexity classes that contain only decidable problems) with the same oracle $O$ that solves the halting problem for a Turing ...
- 345
4
votes
1
answer
161
views
Why is $NP \subseteq P \implies NP^A \subseteq P^A$ false?
My question is about why does the result of Baker-Gill-Solovay not prove that $P \neq NP$. There have been several questions on this forum about this topic perhaps but I couldn't find my specific ...
- 141
3
votes
1
answer
577
views
Proof of $\mathsf{NP}^\mathsf{BPP} \subseteq \mathsf{BPP}^\mathsf{NP}$
How to show that $\mathbf{NP}^{BPP} \subseteq \mathbf{BPP}^{NP}$?
I tried to build $NTM$ $M_{NP1}$, which uses $PTM$ $M_{BPP1}$. Show that there will always be $PTM$ $M_{BPP2}$, which uses $L ($$NTM$ ...
- 31
1
vote
0
answers
90
views
Maximum Query String Length in Oracle Turing Machines
I am learning oracle Turing machines, which is normal Turing machines equipped with a write-only query tape and with access to a query oracle.
My question is, is there a limit of the content that can ...
- 137
1
vote
0
answers
32
views
Does proving P^NP = NP have an implication in the P=NP question?
For language $O$, by $P^O$ I am referring to the set containing every language that can be decided by a polynomial-time deterministic TM with oracle access to $O$ (see Arora and Barak, Chapter 3, ...
- 111
4
votes
1
answer
416
views
Oracle separation P and BPP
I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in ...
- 723
3
votes
1
answer
82
views
Does there exist any unrelativized separation between a quantum complexity class and a classical one?
I'm familiar with results of relativized separation for BPP-BQP, BQP-PH and NPC-BQP. I'm also aware that while e.g. Factoring is not believed to be in BPP, it hasn't been proven and so we're not quite ...
- 133
1
vote
1
answer
46
views
Injectivity verification in o(n) space and O(n) time
The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to ...
- 531
1
vote
1
answer
566
views
Does EXP^EXP = EXP? [duplicate]
Does $\mathrm{EXP}^\mathrm{EXP}=\mathrm{EXP}$?
Here is my thought: $\mathrm{EXP}$ machine can ask $2^{O(n)}$ queries to the oracle, and each oracle would itself solve an exponential time problem in a ...
- 11
1
vote
0
answers
55
views
Which is harder, an NP-complete problem or the Raz-Tal oracle problem?
This is a (hopefully) sharper version of a question that I asked previously.
Which of these algorithms is believed to have a longer asymptotic runtime?
The optimal algorithm guaranteed to solve some ...
- 1,096
6
votes
1
answer
100
views
Do relativized relations between complexity classes tell us anything about the nonrelativized relation?
The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the ...
- 1,096
2
votes
1
answer
178
views
How strong is an oracle that avoid don't-halt
Consider such an oracle:
Given a turing machine[1], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt.
How strong is a TM with the oracle?
Can the ...
- 249
4
votes
1
answer
347
views
Basic complexity theory (in Oracle Separation of BQP and PH)
I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$^O\nsubseteq$ PH$^O$.
Aaronsons paper was helpful, but I still have some ...
- 165
2
votes
1
answer
785
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 ...
- 1,073
3
votes
1
answer
89
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 ...
- 53
3
votes
1
answer
275
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 $\tau_X$ on $...
