Paper 2019/754
Is it Easier to Prove Theorems that are Guaranteed to be True?
Rafael Pass and Muthuramakrishnan Venkitasubramaniam
Abstract
Consider the following two fundamental open problems in complexity theory: (a) Does a hardonaverage language in NP imply the existence of oneway functions?, or (b) Does a hardonaverage language in NP imply a hardonaverage problem in TFNP (i.e., the class of total NP search problem)? Our main result is that the answer to (at least) one of these questions is yes. Both oneway functions and problems in TFNP can be interpreted as promisetrue distributional NP search problemsnamely, distributional search problems where the sampler only samples true statements. As a direct corollary of the above result, we thus get that the existence of a hardonaverage distributional NP search problem implies a hardonaverage promisetrue distributional NP search problem. In other words,” It is no easier to find witnesses (a.k.a. proofs) for efficientlysampled statements (theorems) that are guaranteed to be true.”   This result follows from a more general study of interactive puzzlesa generalization of averagecase hardness in NP—and in particular, a novel roundcollapse theorem for computationallysound protocols, analogous to BabaiMoran's celebrated roundcollapse theorem for informationtheoretically sound protocols. As another consequence of this treatment, we show that the existence of O(1)round publiccoin nontrivial arguments (i.e., argument systems that are not proofs) imply the existence of a hardonaverage problem in NP/poly.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 TFNProundcollapseaveragecase hardness
 Contact author(s)
 muthuv @ cs rochester edu
 History
 20200415: last of 2 revisions
 20190626: received
 See all versions
 Short URL
 https://ia.cr/2019/754
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/754, author = {Rafael Pass and Muthuramakrishnan Venkitasubramaniam}, title = {Is it Easier to Prove Theorems that are Guaranteed to be True?}, howpublished = {Cryptology ePrint Archive, Paper 2019/754}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/754}}, url = {https://eprint.iacr.org/2019/754} }