Questions tagged [relativization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
30
votes
3answers
3k 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 ...
5
votes
1answer
590 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}$-...
7
votes
1answer
1k 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 ...
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 ...
6
votes
2answers
711 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
0answers
181 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 ...
4
votes
1answer
180 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 ...
1
vote
0answers
222 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 \...