# Questions tagged [oracle-machines]

The tag has no usage guidance.

140 questions
Filter by
Sorted by
Tagged with
1 vote
48 views

For a language $L$ to be in $NP$ it suffices for a witness $y$ to exist and a (polynomial) verification algorithm $A$, s.t. $x\in L$ iff there exists a (polynomial size) $y\,$ s.t. invoking $A$ on $x,... 1 vote 1 answer 40 views ### Applications of a SAT Solver Oracle for Determining the Uniqueness of Solutions I am exploring two kinds of model$π_{π,π,k}$and$S_{m,n,k}$within the realm of satisfiability problems (SAT). Formal construction of$π_{π,π,k}$To construct the$π_{π,π,k}$model in ... • 338 3 votes 1 answer 70 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 ... 1 vote 0 answers 43 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,684 1 vote 1 answer 45 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 31 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,684 1 vote 1 answer 56 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_{...
26 views

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
1 vote
54 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
38 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
53 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 ...
1 vote
43 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 ...
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
46 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
63 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
1 vote
65 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 ...
• 129
1 vote
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-...
• 489
1 vote
110 views

47 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
48 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
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,631
70 views

• 31
165 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
313 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
256 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 ...
• 365
416 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 ...
• 365
232 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 ...
• 365
168 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
589 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
92 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
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
441 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
83 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
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 ...
1 vote
589 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
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,116
106 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,116
187 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
353 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
817 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
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 ...
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 \$...