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 hard-on-average language in NP imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average 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 one-way functions and problems in TFNP can be interpreted as promise-true distributional NP search problems---namely, 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 hard-on-average distributional NP search problem implies a hard-on-average promise-true distributional NP search problem. In other words,” It is no easier to find witnesses (a.k.a. proofs) for efficiently-sampled statements (theorems) that are guaranteed to be true.” 
 This result follows from a more general study of interactive puzzles---a generalization of average-case hardness in NP—and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols. As another consequence of this treatment, we show that the existence of O(1)-round public-coin non-trivial arguments (i.e., argument systems that are not proofs) imply the existence of a hard-on-average problem in NP/poly.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
TFNPround-collapseaverage-case hardness
Contact author(s)
muthuv @ cs rochester edu
History
2020-04-15: last of 2 revisions
2019-06-26: received
See all versions
Short URL
https://ia.cr/2019/754
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.