Hacker News new | past | comments | ask | show | jobs | submit login

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



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: