Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

2
votes
0answers
59 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 ...
2
votes
1answer
101 views

What is conjunctive truth table reduction?

What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?
3
votes
1answer
101 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 "...
6
votes
2answers
150 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.
4
votes
2answers
178 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 ...
1
vote
1answer
85 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 ...
9
votes
1answer
223 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....
18
votes
1answer
390 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 ...
6
votes
0answers
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-...
10
votes
2answers
839 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 ...
10
votes
1answer
252 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$ ...
23
votes
3answers
656 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 ...
16
votes
2answers
443 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 ...
5
votes
1answer
278 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 ...
12
votes
0answers
456 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 ...
2
votes
0answers
97 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 ...
5
votes
0answers
299 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 ...
6
votes
1answer
527 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 ...
7
votes
2answers
590 views

Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

A recent question asks whether relativization is well-defined. This question wonders how to put one use of it on firmer ground. In the BGS 1975 proof that there exists a language $B$ such that $...
8
votes
2answers
374 views

Is relativization well-defined?

According to BGS theorem [1], there is an oracle $A$ such that $P^A\neq NP^A$. If the relativization operation $B\mapsto B^A$ was a well-defined function, one would expect that from $B^A\neq C^A$ ...
12
votes
3answers
699 views

What are natural examples of non-relativizable proofs?

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles). Virtually all proofs seem to be relativizable, though. What are good examples of ...
5
votes
0answers
136 views

Relativization of Toda's Theorem

I'm trying to figure out some consequences of the fact that Toda's Theorem relativizes. The (un-relativized) Toda's theorem states that $PH \subset P^{\#P}$ so that for any constant $k$ and any ...
8
votes
1answer
333 views

Techniques for proving that a sentence relativizes

I am interested in how one proves that a sentence relativizes. Of course, proving that a sentence does not relativize is simple, as seen in the Baker-Gill-Solovay result; but how does one prove that ...
3
votes
0answers
60 views

one-way functions vs. secret-coin CRHFs

Is there any paper which can be used to show that there can be no relativizing construction of a secret-coin Collision-Resistant Hash Family from a one-way function and unlike this paper, does not ...
11
votes
1answer
494 views

Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$

I would like to know if there exists a relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$. I am also interested to know if there exists a relativized world where ${\bf P^B} \not = {\bf NP^...
8
votes
1answer
365 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 ...
4
votes
0answers
218 views

Can relativization change the direction of separation?

Are any $A$, $B$, and $O$ such that: $O$ is a set (for oracle), $A$ and $B$ are the names of two known complexity classes, $A^X$ and $B^X$ have well-defined accepted meanings, $A=A^\emptyset\subset B^...
4
votes
0answers
300 views

A natural result that relativized to a random oracle is true with probability 1/2

There are several well known results regarding random oracles, e.g. $\mathsf{IP}^A \neq \mathsf{PSpace}^A$ for almost all oracles. Are there any known natural examples where a similar statement ...
10
votes
4answers
1k views

Oracle results on P vs BPP

Let $A$ be any EXP complete problem. Then, $P^A = NP^A$. Let $B$ be some oracle that takes into accounts the queries that $M$ (a TM in P) will make, and we can get $P^B \neq NP^B$. Question: Do we ...
11
votes
1answer
307 views

Ruzzo-Simon-Tompa oracle access mechanism

In a paper on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some more pathological examples in this vein in ...
18
votes
1answer
784 views

What's the “real” reason that IP=PSPACE is non-relativizing?

IP=PSPACE is listed as the canonical example of a non-relativizing result, and the proof for this is that there exists an oracle $O$ such that ${\sf coNP}^O \not\subseteq {\sf IP}^O$, while ${\sf coNP}...
1
vote
1answer
199 views

Can an oracle allowing errors be non-relativizing?

I am experimenting with k-SAT. I'm using an oracle that returns the total number of satisfiable truth assignments, which is in #P. The interest here is that this total is returned modulo a natural ...
12
votes
1answer
431 views

Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$

Complexity Zoology by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\...
28
votes
1answer
1k views

Toy examples for barriers to $P \ne NP$

Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?
2
votes
0answers
95 views

Abilities of Restricted Relativization in Proving Conjectures

Though everyone seems to say that P vs NP cannot be solved using relativization because there are oracles both $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \neq \text{NP}^B$, why ...
7
votes
1answer
315 views

Separation between existence of crypto primitives

I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My ...
11
votes
4answers
699 views

Does diagonalization captures the essence of class separation ?

I don't remember having seen a class separation not based on diagonalization and relativization results. Diagonalization could still be used to separate remaining known classes, because non-...
63
votes
1answer
3k views

More on PH in PP?

A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were ...
13
votes
0answers
348 views

Oracle relative to which MA does not have a complete problem?

Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called Arthur-Merlin games. The game is played by powerful but untrustworthy wizard ...
12
votes
1answer
351 views

Can relativization results be used to prove sentences formally independent?

Is it possible to demonstrate that a sentence must be formally independent based on the fact that it is non-relativizing? In other words, are there examples of sentences in computability/complexity ...
28
votes
1answer
982 views

Are there canonical non-relativizing techniques?

In a lot of domains, there are canonical techniques which everybody working in the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of not ...
8
votes
2answers
372 views

Relativization with Respect to Non-Recursive Oracles

In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets. ...
10
votes
1answer
223 views

Worlds Relative to Which “Invulnerable Generators” Do Not Exist

Invulnerable generators are defined as follows: Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it ...
6
votes
1answer
763 views

Oracle relative to which BPP = EXP

An oracle construction relative to which BPP = EXP is usually attributed to Heller (Mathematical System Theory Vol. 17, 1984). Unfortunately I don't have the paper available in my library. Could ...
15
votes
1answer
488 views

Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

This is a follow up to this question, and is related to this question of Shiva Kinali. It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use ...