[rmserror]

a complexity theory error: "Just as you can reduce all NP hard problems to 3-SAT..."

you can reduce all NP problems to 3-SAT because 3-SAT is NP complete. you cannot reduce all NP hard problems to 3-SAT. for example, all problems in NP reduce to SUCCINCT-SAT, an NEXP-complete (and therefore NP-hard) set. good luck reducing SUCCINCT-SAT to 3-SAT (despite how little progress in separation of classes we've made, the time hierarchy theorem still indicates this is impossible)

[xmpir]

great response! NP-problem discussions make me happy. for those not understanding a word: http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#...