Reading source record arXiv-1112.2275v3. View default cited record →
The precise statements and locators cited in this P versus NP research record.
Author full version dated March 2014; an extended abstract appeared at CCC 2012. The paper explicitly uses a bounded-error randomized formulation of SETH.
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
If the stated bounded-error randomized SETH holds, then P ≠ NP.
Passage ID: pnp-entry-seth-implies-separation:v1
Source item: seth-implies-separation
Source record: pnp-seth@arXiv-1112.2275v3
For every fixed α in (0,1), there is a fixed clause width k such that k-CNF-SAT on n variables has no bounded-error randomized O(2^{αn})-time algorithm.
Passage ID: pnp-entry-seth:v1
Source item: seth
Source record: pnp-seth@arXiv-1112.2275v3
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
Problem publication v14
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
Only a sufficient stronger premise; P ≠ NP gives no such exponent or randomized lower bound.
Observed Oct 10, 2026
Connection
The cited randomized SETH excludes even fixed-base exponential improvements for some clause width, and therefore excludes polynomial deterministic algorithms.
Source assessment
Open
Unresolved assertion in the cited scope
A fine-grained hardness premise stronger than the deterministic version; neither version follows from P ≠ NP.
Observed Oct 10, 2026
Linked manuscripts, code and data. External proof reports, statement correspondence and OpenMath execution are separate checks.
Manuscript / exposition · external
External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Resource revision: arXiv-1112.2275v3
SHA-256 for this linked file. A matching checksum identifies the same bytes; it does not assess the mathematics.
292ff4c93c0834d4eb560ad0f30b6b703a972901682d5af65b65afcd4c4b0ff1Recorded authorship
Marek Cygan · Holger Dell · Daniel Lokshtanov · Dániel Marx · Jesper Nederlof · Yoshio Okamoto · Ramamohan Paturi · Saket Saurabh · Magnus Wahlström
Marek Cygan; Holger Dell; Daniel Lokshtanov; Dániel Marx; Jesper Nederlof; Yoshio Okamoto; Ramamohan Paturi; Saket Saurabh; Magnus Wahlström
AI involvement is not reported by this cited source; this is not a claim of its absence.
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
Cygan et al. · On problems as hard as CNF-SAT
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Source terms ↗