All Questions

Are there zero-knowledge proofs for every answer to the $P=NP$ question? For instance, if you have a polynomial-time algorithm of moderate complexity for the graph-coloring problem, then it is easy to ...

Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP? Such an oracle ...