English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Consider the following two fundamental open problems in complexity theory:(a) Does a hard-on-average language in NP imply the existence of one-wayfunctions?, or (b) Does a hard-on-average language in NP imply ahard-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-truedistributional NP search problems---namely, distributional search problemswhere the sampler only samples true statements. As a direct corollary of theabove result, we thus get that the existence of a hard-on-averagedistributional NP search problem implies a hard-on-average promise-truedistributional NP search problem. In other words, "It is no easier to findwitnesses (a.k.a. proofs) for efficiently-sampled statements (theorems) thatare guaranteed to be true." This result follows from a more general study ofinteractive puzzles---a generalization of average-case hardness in NP---and inparticular, a novel round-collapse theorem for computationally-sound protocols,analogous to Babai-Moran's celebrated round-collapse theorem forinformation-theoretically sound protocols. As another consequence of thistreatment, we show that the existence of O(1)-round public-coin non-trivialarguments (i.e., argument systems that are not proofs) imply the existence of ahard-on-average problem in NP/poly.

Is it Easier to Prove Theorems that are Guaranteed to be True?