Questions tagged [relativization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
32 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 ...
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 ...
1
vote
0answers
19 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 ...
0
votes
0answers
33 views

Cook-Levin theorem and relativization

An answer in the post How can I show that the Cook-Levin theorem does not relativize? gives a proof that there exists an oracle B and a language L in the class $NP^B$ such that there is no oracle ...
3
votes
1answer
42 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{...
2
votes
1answer
65 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
58 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
vote
1answer
46 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 ...
5
votes
2answers
695 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 ...
4
votes
1answer
170 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 ...
2
votes
1answer
84 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 "...
1
vote
1answer
69 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$ ...
1
vote
0answers
181 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
votes
0answers
42 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 ...
7
votes
1answer
907 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 ...
4
votes
1answer
148 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 ...
4
votes
0answers
178 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 ...
6
votes
2answers
499 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 ...
3
votes
1answer
289 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
vote
1answer
125 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 ...
7
votes
1answer
1k 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 ...
5
votes
1answer
537 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}$-...
10
votes
1answer
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 ...
12
votes
2answers
2k 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 ...
28
votes
3answers
2k 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 ...