# Questions tagged [relativization]

The tag has no usage guidance.

46 questions
Filter by
Sorted by
Tagged with
119 views

### Can relativization technique be applied to natural NP-complete languages?

Levin  defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
62 views

### On reduction between two classes?

https://link.springer.com/article/10.1007/s00153-013-0351-x gives seven reductions $m,c,d,p,btt(1),\ell,tt$. What does norm $1$ mean in $btt(1)$? Is there illustrative examples that help understand ...
121 views

### What is conjunctive truth table reduction?

What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?
124 views

### Almost-P and related definitions

I'm pretty sure this has a trivial answer but it's always faster to ask the community :-) I understand that, relative to a random oracle, P=BPP. But this is sometimes phrased via the shorthand "...
165 views

### What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

In this article Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$. I wanted to know if there are more examples like this.
197 views

### Oracle comparing $EXP$ with $UP$

Heller (Theorem 6) gave an oracle relative to which $NP=EXP$, and Homer & Selman gave an oracle relative to which $P=UP$ and $\Sigma_2^P=EXP$. Beigel, Buhrman, Fortnow (freely available author's ...
89 views

### Is there a relativized form of Rice Theorem?

Suppose $P_1$ and $P_2$ are nontrivial semantic properties of Turing Machines, and suppose that $P_1\wedge P_2$ is nontrivial given $P_1$. Can one claim that $P_1\wedge P_2$ is undecidable given an ...
246 views

### Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

Background We know that $P^{\#P} \subseteq PSPACE$. In addition, we known from Toda's theorem that $PH \subseteq P^{\#P}$. For more background on $\#P$, see here: https://en.wikipedia....
436 views

### What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

Background It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$. It is even known that the separation holds relative to a random oracle. Informally, one may interpret ...
74 views

### Is [2-party d3-rolling with maximum probability 1/2] known to imply one-way functions?

Most things in complexity-based cryptography (for examples, see page 4) are known to imply the existence of one-way functions, especially after this paper proved that implication for weak coin-...
1k views

### Is ALogTime != PH hard to prove (and unknown)?

Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP: Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on diagonalization ...
257 views

### Can a random oracle change which TFNP problems are strongly hard-on-average?

I've been thinking about the following question at various times since I saw this question on Cryptography. Question Let $R$ be a TFNP relation. ​ Can a random oracle help P/poly to break $R$ ...
715 views

### Is there a result in computability theory that does not relativize?

I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that Our axiomatization has its limit: it cannot prove any results in computability ...
445 views

### Potentially equal complexity classes without known contradictory relativizations

What are some examples of pairs of complexity classes $A$ and $B$ such that we do not know whether $A=B$, and we do not know contradictory relativizations either (i.e., we do not know oracles $P$ and ...
319 views

### Relativized world where $L^A=NP^A$

I wonder1 whether there is a known relativization barrier against proving $L\neq NP$. Hence I'm looking for a language $A$ for which $L^A=NP^A$. My first idea was to try $A:=SAT$, but then I thought ...
502 views

### Impact of proof of NP=co-NP on RP vs co-RP Question?

It is known that P ⊆ RP ⊆ NP and P ⊆ co-RP ⊆ co-NP. In an oracle world: If NP=co-NP, does RP=co-RP=ZPP follow automatically or does it require additional conditions? If NP=PSPACE, does RP=co-RP=ZPP ...
125 views

### Introduction to Black-Box Separations in Cryptography

Are there any textbook-style material on black-box separations in cryptography? I tried to read the paper of Impagliazzo and Rudich but couldn't get much of it. A previous StackExchange entry gives a ...
337 views

### An oracle relative to which EXP(NP) = BPP

Whether or not $\mathbf{BPP} = \mathbf{EXP}^{\mathbf{NP}}$ is an open problem, although we believe the former is strictly contained in the other. I guess, from the absence of the proof of the ...
587 views

### Does the Cook-Levin theorem relativize?

My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes. If you have a proof that the ...
770 views

371 views

### Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor?

Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula $$s(L)_n=\chi_L(s(L)_{<n})$$ Here $\chi_L$ is the characteristic ...
223 views