openmath.dev
Esc

Loading…

↑ ↓ to move↵ to open

Appearance
Appearance

Theorem · version 1

If P ≠ NP, intermediate problems exist

Earlier version 1. View current version 2 →

Statement

If P ≠ NP, then some languages in NP are neither in P nor NP-complete under polynomial-time many-one reductions.

Assumptions

  • P ≠ NP; polynomial-time many-one completeness.

Scope

Existence of NP-intermediate languages; not a classification of specific natural candidates.

Evidence

Connections

In this problem · publication v6 · Selected context

P versus NP →

Conditional implication · Proved

This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.

This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.

Relationship not independently reviewed. This concerns its use in this problem.

In this problem · publication v7

P versus NP →

Conditional implication · Proved

This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.

This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.

Relationship not independently reviewed. This concerns its use in this problem.

Sources

Avi Wigderson · Mathematics and Computation →

  • Theorem 4.1 [Lad75], §4.2 → · Original passage ↗
    Recorded wording

    If P ≠ NP, then some languages in NP are neither in P nor NP-complete under polynomial-time many-one reductions.

    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.

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.

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.

Record details
Claim ID
claim-pnp-ladner
Statement version
1
SHA-256
2ef20e099a6b4250fdafffd22156bb418254fbd41fa60fdf27fa9f595faa27c7

Publication records