News for hackers. Stuff that matters.
Re:The Boolean Satisfiability Problem and SAT Solvers by DerekL on Thursday June 08, 2017 @03:30AM (#14512558)
No, the article is correct. Wikipedia says, “A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time.” They cite the paper “The complexity of theorem-proving procedures”, Stephen A. Cook (1971), which says:

    It is shown that any recognition
    problem solved by a polynomial time-
    bounded nondeterministic Turing
    machine can be "reduced" to the pro-
    blem of determining whether a given
    propositional formula is a tautology.
https://en.wikipedia.org/wiki/NP-completeness http://dl.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047

There are no comments on this comment yet.