Open
Unresolved assertion in the cited scope ↗
Avi Wigderson · Mathematics and Computation · Definition 4.7 and §4.5 →
Observed Oct 10, 2026
Conjecture · version 1
Standard one-way functions exist
Earlier version 1. View current version 2 →
Statement
There exists a polynomial-time-computable function that is hard to invert on average for probabilistic polynomial-time algorithms.
Assumptions
- The standard asymptotic cryptographic definition, efficient sampling and polynomially bounded encodings.
Scope
Average-case cryptographic hardness; stronger than merely worst-case NP hardness.
Evidence
Source reports
Connections
In this problem · publication v5 · Selected context
P versus NP →
Different statement · related variant · Open
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
One-way implication
Average-case one-wayness is a stronger sufficient hardness premise.
P ≠ NP alone does not establish one-way functions or the security of a particular cryptosystem.
Details & sources
Standard one-way functions exist →
Open · version 1
There exists a polynomial-time-computable function that is hard to invert on average for probabilistic polynomial-time algorithms.
- The standard asymptotic cryptographic definition, efficient sampling and polynomially bounded encodings.
Scope: Average-case cryptographic hardness; stronger than merely worst-case NP hardness.
P ≠ NP →
Open · version 2
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
One-way functions would separate P and NP →
Relationship statement · Proved · version 1
If standard one-way functions exist, then P ≠ NP.
- Standard polynomially bounded one-way functions; classical polynomial-time computation.
Scope: The reverse implication is not established; P ≠ NP alone is not a security guarantee.
Relationship not independently reviewed.
Connection in P versus NP →Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v7
P versus NP →
Different statement · related variant · Open
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
One-way implication
Average-case one-wayness is a stronger sufficient hardness premise.
P ≠ NP alone does not establish one-way functions or the security of a particular cryptosystem.
Details & sources
Standard one-way functions exist →
Open · version 1
There exists a polynomial-time-computable function that is hard to invert on average for probabilistic polynomial-time algorithms.
- The standard asymptotic cryptographic definition, efficient sampling and polynomially bounded encodings.
Scope: Average-case cryptographic hardness; stronger than merely worst-case NP hardness.
P ≠ NP →
Open · version 2
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
- Finite binary inputs; uniform classical computation; polynomial time in bit length.
Scope: The conjectural negative answer to the same canonical question.
One-way functions would separate P and NP →
Relationship statement · Proved · version 1
If standard one-way functions exist, then P ≠ NP.
- Standard polynomially bounded one-way functions; classical polynomial-time computation.
Scope: The reverse implication is not established; P ≠ NP alone is not a security guarantee.
Relationship not independently reviewed.
Connection in P versus NP →Relationship not independently reviewed. This concerns its use in this problem.
Sources
Avi Wigderson · Mathematics and Computation →
- Definition 4.7 and §4.5 → · Original passage ↗
Recorded wording
There exists a polynomial-time-computable function that is hard to invert on average for probabilistic polynomial-time algorithms.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
- §4.4–4.5, Definition 4.7 and discussion → · Original passage ↗
Recorded wording
If standard one-way functions exist, then P ≠ NP.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Avi Wigderson · Published · Publication date 2019
Published author exposition or original paper.
Avi Wigderson · Mathematics and Computation — proof text ↗Manuscript / exposition · external
Revision & attribution
Source revision: author-draft-2019-08-06. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Avi Wigderson · Mathematics and Computation — proof text: author-draft-2019-08-06. External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Stephen Cook · The P versus NP problem →
- Problem statement and discussion, pp. 2–3 → · Original passage ↗
Recorded wording
There exists a language in NP that is not decidable by any deterministic polynomial-time algorithm.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Stephen Cook · Published
Published author exposition or original paper.
Revision & attribution
Source revision: official-description-sha256-018f3d473d16. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Open
Unresolved assertion in the cited scope ↗
Observed Oct 10, 2026 · Source passage →
Record details
- Claim ID
- claim-pnp-one-way
- Statement version
- 1
- SHA-256
- 7e7565b05ab4517a50bbbffbe70547c8de50f485d51d489e4441425f7cc34d13