# Tagged Questions

The tag has no usage guidance.

647 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 ...
214 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. As mentioned in my bounty message: I would accept a proof that the implication ...
288 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 ...
399 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$ ...
233 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 ...
303 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 ...
75 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 ...
169 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 ...
340 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 ...
380 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 ...
298 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$ ...
612 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 ...
120 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 ...
301 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 ...
58 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 ...
416 views

289 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 ...
915 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 ...
236 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 ...
595 views

943 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?
92 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 ...
283 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 ...
604 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-...
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 ...
322 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 ...
316 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 ...
894 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 ...
353 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. ...
205 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 ...