Questions tagged [relativization]
The relativization tag has no usage guidance.
33
questions
3
votes
3
answers
224
views
Question about the Relativization barrier
Baker, Gill, and Solovay has shown in their famous paper, that there are oracles $A$ and $B$ with $P^A = NP^A$ and $P^B \not= NP^B$. So, one can't solve the $P$ vs. $NP$ Problem
with methods like ...
1
vote
0
answers
32
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-...
- 407
3
votes
0
answers
28
views
Understanding a black-box vs white-box simulation and relativization
I am trying to understand the relativization barrier from Baker Gill Solovay (BGS).
About this barrier, I have heard that it only applies when using a black-box simulation. Hence, my question is, what ...
- 407
3
votes
1
answer
105
views
Show that $P^A \neq EXP^A$ for all oracles A
I knew that $P \neq EXP$ by Time Hierarchy Theorem. But, I'd like to show that $P^A \neq EXP^A$ for all oracles A. How can I do it?
I knew that If I make A=EXP, PSPACE, NP, and many others, then this ...
- 729
1
vote
0
answers
66
views
How do we know that this Karp-Lipton theorem is derived from relativizing arguments?
Luca Trevisan wrote, " The oracle $C$ tells us that we cannot have a relativizing proof that derives the $𝑁𝑃 ⊈ 𝑃/𝑝𝑜𝑙𝑦$ conclusion from the $𝑃 ≠𝑁𝑃$ assumption, so a theorem such as Karp-...
- 729
2
votes
1
answer
194
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
4
votes
1
answer
152
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
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,034
6
votes
1
answer
95
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,034
4
votes
1
answer
52
views
Finding a language that is $NP^L$-complete
I'm trying to prove a theorem and as a lemma I would like to identify an $NP^L$-complete language. I was thinking something like a machine that can decide $SAT$ equipped with an oracle for $L$ can ...
- 205
3
votes
1
answer
86
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 ...
- 43
1
vote
0
answers
22
views
Any barrier result for this kind of (non-relativising) technique?
We think that non-deterministic machines are more powerful than deterministic machines, by giving an oracle access to $P\subseteq L\subseteq NP$, it seems reasonable to expect there's some $L$ that is ...
- 271
4
votes
1
answer
464
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{ ...
- 41
1
vote
1
answer
446
views
Is the existence of an oracle such that $P^O = NP^O$ nontrivial? [duplicate]
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 ...
- 1,034
3
votes
1
answer
103
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 =...
- 1,034
1
vote
1
answer
60
views
A' not computable in A
Recall A'= $\{x \mid \phi^A_x(x)$ halts and accepts $\}$
In this article, a proof that A' not computable in A is given:
http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Flood.pdf
He ...
- 139
7
votes
2
answers
848
views
Can two different complexity classes be equal relative to an oracle? Example request
Is there a known example of two complexity classes, $A$ and $B$, such that:
$A \neq B$;
there is an oracle $O$ for which $A^O = B^O$?
I strongly believe that there are such examples, as otherwise $P ...
- 213
4
votes
1
answer
245
views
Can two equal classes be separated wrt an oracle?
Is it known if there are two classes of languages $A$ and $B$ such that:
$A$ and $B$ are defined wrt the exact same type of machine (e.g. 1-tape Deterministic Turing Machines, 2-tape Deterministic ...
- 213
2
votes
1
answer
150
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 "...
- 43
1
vote
1
answer
100
views
Relativized world where $LogCFL^A=PSPACE^A$
I wonder whether there is a known relativization barrier against proving $LogCFL\neq PSPACE$. Hence I'm looking for a language $A$ for which $LogCFL^A=PSPACE^A$.
One could try $A:=TQBF$, where $TQBF$ ...
- 5,382
1
vote
0
answers
249
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 \...
- 4,282
4
votes
0
answers
56
views
Complete problems and relativization barriers for nonuniform complexity classes
Do nonuniform complexity classes like NP/poly have complete problems?
Are there relativization barriers for separations of nonuniform complexity classes?
One way to interpret the second question is ...
- 5,382
10
votes
1
answer
3k
views
How can I show that the Cook-Levin theorem does not relativize?
The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) :
Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not ...
- 2,932
4
votes
1
answer
214
views
Is $BQP$ in $P^{NP}$?
I read in the introduction of this paper
http://www.scottaaronson.com/papers/uncompute.pdf
that there is a problem $B$ such that $BQP^B \not\subset P^{NP^B}$, and that $B$ is in $BPP$. But, using ...
- 143
4
votes
0
answers
228
views
Relativization of NP-completeness [duplicate]
This is actually exercise 3.7 from "Computational Complexity: A Modern Approach".
I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. I need to show that that exists some ...
- 13.3k
9
votes
2
answers
1k
views
The meaning of relativization
I don't understand the notion of relativization. I expose with an example. Consider a class $A$ that contains $P$, e.g. $NP$. Why $P^A$ is not necessarily equal to $A$? I can naively think that if one ...
- 221
3
votes
1
answer
480
views
Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?
I learned from this post that ${\sf DTIME}^{\text{EXP}}(n^k) \neq \text{EXP}$ for a fixed $k$ for otherwise the Time Hierarchy Theorem would fail in that relativized world. However, is it possible to ...
- 1,611
1
vote
1
answer
179
views
Why does the principle of locality of computation not relativize?
Although I have trouble understanding oracle TMs, I appreciate that non-relativizing techniques will be needed to resolve P vs. NP (as well as most other open problems in TCS). However, one of the ...
- 1,611
7
votes
1
answer
2k
views
Why are non-relativizing proofs preferred to relativizing ones?
I apologize, but even after these two other posts: here and here
I'm still having trouble understanding oracle TMs and relativization. This question comes at the issue from a different angle:
Why ...
- 1,611
6
votes
1
answer
792
views
Confusion about the Time Hierarchy Theorem and relativization
I know that $\mathsf{P}^A = \mathsf{EXP}$
for any $\mathsf{EXPTIME}$-complete language $A$.
Is it true that $\mathsf{DTIME}^A(n^k) = \mathsf{EXP}$
for any fixed $k$ and any $\mathsf{EXPTIME}$-...
- 1,611
10
votes
1
answer
1k
views
Intuition behind Relativization
I take course on Computational Complexity. My problem is I don't understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will ...
- 3,149
12
votes
2
answers
4k
views
An oracle to separate NP from coNP
How to prove that $\mathsf{NP}^A \neq \mathsf{coNP}^A$ ? I am just looking for a such oracle TM $M$ and a recursive language $L(M) = L$ for which this holds.
I know the proof where you show that ...
- 351
34
votes
3
answers
4k
views
Why is Relativization a barrier?
When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to ...
- 609