People who code: we want your input. Take the Survey

# Questions tagged [relativization]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
25 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-...
68 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 ...
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 ...
69 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 ...
88 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 ...
32 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 ...
40 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 ...
51 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 ...
21 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 ...
57 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 ...
243 views

48 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 ...
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 ...
650 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}$-...
684 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 ...
183 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 ...
193 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 ...
337 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 ...
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 ...
145 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 ...
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 ...