§1–2, k-SAT exponential complexity and hypothesis
If ETH holds, then P ≠ NP.
Passage details
Passage ID: pnp-entry-eth-implies-separation:v1
Source item: eth-implies-separation
Source record: pnp-eth@JCSS-2001
Impagliazzo–Paturi · On the complexity of k-SAT
PublishedPublication date Mar 2001
Open paper ↗Reading source record JCSS-2001. View default cited record →
Overview
The precise statements and locators cited in this P versus NP research record.
Published author exposition or original paper.
Passages
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
Passage index · 2
§1, definition of s_k and the exponential-time hypothesis
3SAT cannot be decided in deterministic time 2^{o(n)} times a polynomial in the input length, where n is the number of variables.
Passage details
Passage ID: pnp-entry-eth:v1
Source item: eth
Source record: pnp-eth@JCSS-2001
Used in
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
P versus NP →
Problem publication v14
ETH would separate P and NP →
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
A sufficient stronger hardness hypothesis; P ≠ NP does not establish ETH.
Observed Oct 10, 2026
Connection
ETH rules out even subexponential 3SAT algorithms in the stated model.
Exponential Time Hypothesis →
Source assessment
Open
Unresolved assertion in the cited scope
A stronger quantitative hypothesis than P ≠ NP.
Observed Oct 10, 2026
Problem context · 2 citations
Files
Linked manuscripts, code and data. External proof reports, statement correspondence and OpenMath execution are separate checks.
Impagliazzo–Paturi · On the complexity of k-SAT — proof text ↗
Manuscript / exposition · external
External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Resource revision: JCSS-2001
File checksum
SHA-256 for this linked file. A matching checksum identifies the same bytes; it does not assess the mathematics.
1b7d20af963735666020e844f8a454fbb64893a5f3b3c488c99d1f4bdae5c11cCredits
Recorded authorship
Russell Impagliazzo · Ramamohan Paturi
Russell Impagliazzo; Ramamohan Paturi
AI involvement not reported
AI involvement is not reported by this cited source; this is not a claim of its absence.
Versions
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
- JCSS-2001 · selectedObserved Oct 10, 2026 · used in current publications
Impagliazzo–Paturi · On the complexity of k-SAT
Record details
- Source ID
- pnp-eth
- Record ID
- pnp-eth@JCSS-2001
- Recorded title
- Impagliazzo–Paturi · On the complexity of k-SAT
- Revision
- JCSS-2001
- Observed
- Oct 10, 2026
- Source updated
- Not recorded
- Content SHA-256
- 1b7d20af963735666020e844f8a454fbb64893a5f3b3c488c99d1f4bdae5c11c
- Update method
- Manual primary-source check; changes require a new source version and staff publication.
- Identifier policy
- Source URL and exact theorem/section locator; no inferred identity merge.
- Check interval
- 30 days
- Rights
- metadata-link
- License
- Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Source terms ↗