  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.
