Which Problems Have Strongly Exponential Complexity?

• p. 18

  R. Paturi, P. Pudla´k, and F. Zane, Satisfiability coding lemma, in ‘‘Proceedings of the 3

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: the reviewer reports that Crossref records first page 566 for doi:10.1109/sfcs.1997.646146. The page image shows 'pp. 567–574'. The external page number cannot be checked from the files, so this is a query for the authors.

Second check: another model agreed, code check

• p. 19 Reference 37

  SIAM J. Comput. 7 (1977), 537–546.

• p. 19 Reference 37

  SIAM J. Comput. 7 (1977), 537–546

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: the paper appeared in SIAM J. Comput. vol. 6, no. 3 (1977), and the reviewer reports Crossref volume 6 for doi:10.1137/0206038. The page image shows volume 7. Nothing in the files settles this internally.

Second check: another model agreed

• p. 1 Abstract

  k-Set Cover, Independent Set, Clique, and Vertex Cover, are SERF-complete for the class SNP

• p. 6 Section 1.1

  are SERF-equivalent to these, but are technically not in SNP

• p. 15 Theorem 5

  The following problems are Size-Constrained SNP Complete

• p. 1 Abstract

  k-Colorability, k-Set Cover, Independent Set, Clique, and Vertex Cover, are SERF-complete for the class SNP

Only the authors can say what is right here.

Judge's note: I looked at the abstract (p.1), the end of Section 1.1 (p.6, journal p.517) and Theorem 5 (p.15, journal p.526). The abstract names these problems as SERF-complete for SNP. The body says that Independent Set and k-Set Cover are not in SNP and proves completeness for Size-Constrained SNP. The abstract's wording is therefore stronger than what the body states. It probably means SERF-equivalent; the authors should confirm the intended claim.

Second check: another model agreed

• p. 11 Paragraph after Lemma 2

  C is set to be Σ_{i=1}^k (θ_{i−1}−1)

• p. 12 Sentence after Lemma 7

  setting C=Σ_{i=1}^{k−1} θ_i

• p. 11 After Lemma 2

  C is set to be Σ_{i=1}^{k} (θ_{i−1} − 1)

• p. 12 Sentence after Lemma 7

  The Theorem then follows from Lemmas 1, 2 (setting C=Σ_{i=1}^{k−1} θ_i), and 7

Only the authors can say what is right here.

Judge's note: I checked pp.9-12. θ_0=2 is defined on p.520, and Lemma 2 bounds the number of i-sets by (θ_{i−1}−1)n. Summing gives C = 1 + Σ_{i=1}^{k−1}(θ_i − 1) = Σ_{i=1}^{k−1}θ_i + 2 − k. For k=2 the two values agree. For k≥3 the second is larger and so still a valid bound. For k=1 the first gives 1 and the second gives the empty sum 0, which cannot bound up to n singletons. The closing step of the proof is therefore faulty at k=1, but Theorem 1 itself stands with the p.522 constant.

Second check: another model agreed

• p. 11 Definition of J_i(T)

  no element x appears in more than 2θ_{i−1}−1 sets of size i

• p. 11 Lemma 3 statement

  no element x appears in more than 2θ_{i−1} sets of size i in

• p. 11 Lemma 3 statement

  no element x appears in more than 2hi−1 sets of size i in T

• p. 11 definition of J_i

  no element x appears in more than 2hi−1 −1 sets of size i in T

Only the authors can say what is right here.

Judge's note: Page 11 image: the definition paragraph reads "J_i(T) is the condition that no element x appears in more than 2θ_{i−1}−1 sets of size i in T". The Lemma 3 statement reads "…in more than 2θ_{i−1} sets of size i in T". The proof ends "no element x is contained in more than 2θ_{i−1}−1 i-sets". Lemma 4 likewise states 2θ_{i−1}, and its proof on p.12 concludes 2θ_{i−1}−1. The stated bound is weaker than the defined one, so it is still true and the results stand, but the statement does not match the invariant it names. The authors should say which bound is meant.

Second check: another model agreed

• p. 12 Proof of Lemma 7, last sentence

  ≤ 2k/(αβ_{k−1}) log(k/(αβ_{k−1})) since k/(αβ_{k−1}) ≤ 1/2

• p. 12 Proof of Lemma 7, explanation following the exponential-bound chain

  h(k/(αβₖ₋₁)) ≤ 2k/(αβₖ₋₁) log(k/(αβₖ₋₁))

• p. 12 Proof of Lemma 7, sentence after the display chain

  The first inequality follows from h(k/(αβ_{k−1})) ≤ 2k/(αβ_{k−1}) log(k/(αβ_{k−1})) since k/(αβ_{k−1}) ≤ 1/2

Only the authors can say what is right here.

Judge's note: I read the step on the page image for PDF page 12. Let δ = k/(αβ_{k−1}). The proof itself assumes δ ≤ 1/2, so log2 δ ≤ −1 and the printed right-hand side 2δ·log δ is negative. The binary entropy h(δ) is positive for 0<δ<1, so the inequality is false as printed. Example: δ = 1/4 gives h = 0.811, while the printed RHS is 2·(1/4)·(−2) = −1. The display chain just above uses 2^{((2k/α) log(αβ_{k−1}/k)) n}. That matches the correct bound h(δ) ≤ 2δ log(1/δ). So only the stated justification is wrong. Lemma 7 still holds once the argument is inverted. Under the derivation rule, a faulty step whose stated result stands gets S3 and the author_query bucket.

Second check: another model agreed

• p. 16 Section 4, proof setup

  F accepts O(2^{εn}) inputs

• p. 16 Proof of Theorem 6, second paragraph

  F accepts O(2^{εn}) inputs and F^{−1}(1) ⊆ f^{−1}(1)

• p. 16 proof of Theorem 6

  F accepts O(2en) inputs

Only the authors can say what is right here.

Judge's note: I checked the crop and the full page image: the symbol is printed as a roman O, not Ω. The circuit has fewer than s·2^{εn} < 2^{(1−ε)n} sparse CNFs, and together they cover f^{-1}(1), which has Ω(2^n) points. So by pigeonhole some F accepts at least about 2^{εn}/c inputs. This is a lower bound. The text then uses "|A| ≥ 2^{εn}" and says F "accepts a large set of inputs", both of which need a lower bound. An O(·) bound does not follow from the argument and does not support the next step. The fix is to write Ω and absorb the constant factor. The theorem stands, so the severity is S3 under the derivation rule.

Second check: another model agreed

• p. 16 Proof of Theorem 6, definition of the shattering parameter

  let l be the least integer such that

• p. 16 Immediately following the definition of l

  there is a set of l variables which are shattered by A.

• p. 16 Proof of Theorem 6, paragraph beginning 'Let A = F^{-1}(1)'

  let l be the least integer such that Σ_{i=1}^{l} (n choose i) > |A| ≥ 2^{εn}

Only the authors can say what is right here.

Judge's note: I read the definition on the crop and on the page image; the sum starts at i=1. Sauer–Shelah guarantees d shattered variables only when |A| > Σ_{i=0}^{d−1} C(n,i). Minimality of l gives only |A| ≥ Σ_{i=1}^{l−1} C(n,i), which is below that threshold. I checked a counterexample: n=4 and A = {0000, 1000, 0100, 0010, 0001}, so |A| = 5. Then Σ_{i=1}^{1} = 4 ≤ 5 and Σ_{i=1}^{2} = 10 > 5, so l = 2. But no pair of coordinates ever takes the value 11, so no 2-set is shattered. A does shatter l−1 variables, and l−1 = Ω(n) still holds, so Theorem 6 stands. Under the derivation rule this is S3 with the author_query bucket.

Second check: another model agreed

• p. 1 Footnote 1

  US-Checkoslovakia Science and Technology Program

• p. 17 Ref 5

  M. Szeged

• p. 17 Ref 1

  R. G. Downe

• p. 18 Ref 24

  Opimization

Judge's note: I checked the footnote image on p.1 and the reference list images on pp.17-18. All of the quoted misspellings are present. Szeged/Szegedy is an inconsistency within the paper's own reference list. Rests on outside knowledge: "R. G. Downe" in ref 1 should be Downey (the author's real name), so that item needs author confirmation.

Second check: none (judge only)

• p. 1 Abstract

  there have been a progression of better

Judge's note: Seen in the abstract image on p.1. This is a number-agreement slip; it could pass as notional agreement with "algorithms".

Second check: none (judge only)

• p. 2 Introduction, second paragraph

  sparse k-CNF formulas, More precisely

Judge's note: Seen in the p.2 image. A capitalised new sentence follows a comma.

Second check: none (judge only)

• p. 2 Introduction para 1

  the complexity of specific, natural problems have been shown

Judge's note: Seen in the p.2 image. The fix is "has been shown".

Second check: none (judge only)

• p. 5 Proof of Proposition 1

  R(x, y) on inputs of size n and m(n)

Judge's note: Seen in the p.5 image. The notation is inconsistent but harmless: m(n) can be read as the bound for inputs of length n.

Second check: none (judge only)

• p. 6 Displayed formula for k-SAT ∈ SNP

  I_{s_i}(S, y)

• p. 6 Displayed SNP formula for k-SAT

  ∨_{1≤i≤k} I_{s_i}(S, y)

Judge's note: The p.6 image shows y without a subscript. The quantified variables are y_1,...,y_k, so the y in the disjunct is free, and the clause semantics need y_i. The missing index has an evident fix.

Second check: none (judge only)

• p. 7 Section 1.2, second paragraph

  proving a lower bounds of the form

Judge's note: Seen in the p.7 image.

Second check: none (judge only)

• p. 10 Paragraph after algorithm Reduce

  one child is created by the adding the petals

• p. 10 paragraph after Reduce

  created by the adding the petals

Judge's note: Seen in the p.10 image. The parallel clause in the same sentence reads "created by adding the heart".

Second check: none (judge only)

• p. 12 Proof of Lemma 7

  The first inequality follows from h(k/(αβk−1)

Judge's note: Page 12 image: "h(k/(αβ_{k−1})" opens two parentheses and closes only one before the ≤ sign.

Second check: none (judge only)

• p. 13 Proof of Lemma 8

  2^{(ε/ZC) m2(x')}

Judge's note: Page 13 image and text layer (line 687) both show "ε/ZC". The reduction used is N_{ε/(2C)}, and the next term in the same line uses ε/2C, so "Z" is a slip for "2".

Second check: none (judge only)

• p. 13 Proof of Lemma 8

  m3(y)) = O(m2(x'))

• p. 13 Proof of Lemma 8

  m_3(y)) = O(m_2(x′))

• p. 13 Proof of Lemma 8, time bound

  2^{(ε/ZC) m_2(x′)}

Judge's note: Page 13 image: "Then m3(y)) = O(m2(x′))…" has an unbalanced parenthesis. This cluster also mentions the ε/ZC slip, which is judged under C019.

Second check: none (judge only)

• p. 14 End of page, after definition of Size-Constrained SNP

  quantifiers followed by a universal first-order formula.

Judge's note: Page 14 image: the proof of Theorem 4 already ends with its own ∎. A second ∎ ends the paragraph that defines Size-Constrained SNP, which is not a proof.

Second check: none (judge only)

• p. 14 Proof of Lemma 10

  For every clause x1..., ∨ xj with j ≤ k

• p. 14 Proof of Lemma 10

  For every clause x_1..., ∨ x_j

Judge's note: Page 14 image and text layer (line 742) both show the malformed clause, with a stray comma and the first ∨ missing.

Second check: none (judge only)

• p. 15 Proof of Theorem 5

  any problem in Size-Constrained strong many-one reduces to k-SAT

• p. 15 Theorem 5 statement

  k-Colorability Independent Set

• p. 15 Proof of Theorem 5

  any problem in Size-Constrained strong many-one reduces

• p. 15 Theorem 5

  k-Colorability Independent Set, Vertex Cover

Judge's note: Page 15 image confirms the truncated class name. The missing comma in the Theorem 5 list, also mentioned in this cluster, is judged under C025.

Second check: none (judge only)

• p. 15 Theorem 5 statement

  k-Colorability Independent Set, Vertex Cover

Judge's note: Page 15 image shows no comma between the two problem names. Other lists in the paper (e.g., the abstract) separate them with commas.

Second check: none (judge only)

• p. 16 Section 4, second paragraph after Corollary 4

  this implies that s ≥ 2^{(1−2εn)}

• p. 16 Proof of Theorem 6, end of second paragraph

  this implies that s ≥ 2^{(1−2εn)} and the theorem follows

• p. 16 proof of Theorem 6

  this implies that s \ 2(1−2en)

Judge's note: Checked the page image and crop. The exponent is printed (1−2εn), with n inside the parentheses. Three lines earlier the paper assumes s < 2^{(1−2ε)n}, and the section's goal and closing sentence use 2^{(1−2ε)n}. This is a misplaced parenthesis, not an extraction artefact. The intended bound is clear and the result is unaffected.

Second check: none (judge only)

• p. 17 Reference 1

  R. G. Downe

• p. 17 Reference 5

  M. Szeged

• p. 18 Reference 19

  H. Luckhard

• p. 18 Reference 7

  R. Beigel and R. Eppstein

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: the correct names are R. G. Downey, D. Eppstein and H. Luckhardt. Szegedy is confirmed internally, since refs. 10 and 32 spell it 'M. Szegedy' while ref. 5 prints 'M. Szeged'. The page images show all four printed forms exactly as quoted. These are cosmetic citation slips.

Second check: none (judge only)

• p. 18 Reference 24

  Opimization, approximation and complexity classes

• p. 18 Reference 16

  Some optimal inapproxibility results

• p. 18 Reference 25

  Mat. Zameti

Judge's note: Page 18 image shows all three as quoted. 'Opimization' and 'inapproxibility' are evident misspellings of Optimization and inapproximability. 'Zameti' for the journal Mat. Zametki rests on outside knowledge of the journal's name.

Second check: none (judge only)

• p. 19 Reference 31

  Power indices and easier hand problems

Judge's note: Page 19 image shows 'hand'. In context (power indices for NP-hard problems) 'hand' is an evident typo for 'hard'. The exact title rests on outside knowledge.

Second check: none (judge only)