Skip to main content

Questions tagged [oracle-machines]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
2 answers
48 views

Up to a certain number of witnesses, say 4

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,...
Benicio Agüero's user avatar
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 ...
Jxb's user avatar
  • 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 ...
Zee's user avatar
  • 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 ...
Theorynoob's user avatar
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}$. ...
rus9384's user avatar
  • 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$...
Meki21's user avatar
  • 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 ...
rus9384's user avatar
  • 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_{...
Laurus Laurus's user avatar
0 votes
1 answer
26 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 ...
dino-t's user avatar
  • 23
1 vote
1 answer
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 ...
Loic Stoic's user avatar
0 votes
0 answers
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 ...
Loic Stoic's user avatar
2 votes
1 answer
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 ...
Soham Chatterjee's user avatar
1 vote
1 answer
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 ...
Fivefolded's user avatar
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 ...
lombardo2's user avatar
  • 121
1 vote
1 answer
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 ...
nosyarg's user avatar
  • 232
0 votes
1 answer
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"...
vengaq's user avatar
  • 101
1 vote
0 answers
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 ...
Ondolin's user avatar
  • 129
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-...
441Juggler's user avatar
1 vote
1 answer
110 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 ...
Alonso Montero's user avatar
0 votes
1 answer
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?
Colonizor48's user avatar
0 votes
1 answer
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) ...
Colonizor48's user avatar
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 ...
Ari's user avatar
  • 1,631
2 votes
1 answer
70 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(...
CSDude101's user avatar
  • 121
1 vote
1 answer
169 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 ...
Athena's user avatar
  • 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 ...
StackMachine's user avatar
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 ...
Amit wadhwa's user avatar
0 votes
1 answer
149 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 ...
Amit wadhwa's user avatar
2 votes
0 answers
183 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 ...
user127875's user avatar
2 votes
2 answers
352 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 ...
xdavidliu's user avatar
  • 858
0 votes
1 answer
160 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 ...
Adam G's user avatar
  • 31
2 votes
1 answer
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}$
blademan9999's user avatar
2 votes
1 answer
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$? ...
Ben's user avatar
  • 51
2 votes
1 answer
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 ...
DeeDee's user avatar
  • 365
6 votes
1 answer
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 ...
DeeDee's user avatar
  • 365
2 votes
3 answers
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 ...
DeeDee's user avatar
  • 365
4 votes
1 answer
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 ...
kishlaya's user avatar
  • 141
3 votes
1 answer
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$ ...
Katy's user avatar
  • 31
1 vote
0 answers
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 ...
Snjór's user avatar
  • 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, ...
pysolver's user avatar
  • 111
4 votes
1 answer
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 ...
Vincent's user avatar
  • 723
3 votes
1 answer
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 ...
user976850's user avatar
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 ...
Mario Carneiro's user avatar
1 vote
1 answer
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 ...
fgdhdfg's user avatar
  • 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 ...
tparker's user avatar
  • 1,116
7 votes
1 answer
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 ...
tparker's user avatar
  • 1,116
2 votes
1 answer
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 ...
l4m2's user avatar
  • 249
4 votes
1 answer
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 ...
Sebastian's user avatar
  • 165
2 votes
1 answer
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 ...
Yamar69's user avatar
  • 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 ...
SAS's user avatar
  • 53
3 votes
1 answer
277 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 $...
Daniel Neugebauer's user avatar