Citation Hunt

Leaderboard

The Wikipedia snippet below is not backed by a reliable source. Can you find one?

Click I got this! to go to Wikipedia and fix the snippet, or Next! to see another one. Good luck!

In page Boolean satisfiability problem:

This text has been unreferenced on Wikipedia for a very long time. If you can't find a source, be bold and remove it!

"

Some authors restrict k-SAT to CNF formulas with exactly k literals.[citation needed] This does not lead to a different complexity class either, as each clause l1 ∨ ⋯ ∨ lj with j < k literals can be padded with fixed dummy variables to l1 ∨ ⋯ ∨ lj ∨ dj+1 ∨ ⋯ ∨ dk. After padding all clauses, 2k–1 extra clauses[7] must be appended to ensure that only d1 = ⋯ = dk = FALSE can lead to a satisfying assignment. Since k does not depend on the formula length, the extra clauses lead to a constant increase in length. For the same reason, it does not matter whether duplicate literals are allowed in clauses, as in ¬x ∨ ¬y ∨ ¬y.