Ask HN - Why 3SAT?

[bartonfink]

Hey, everyone -

The recent buzz over the 3SAT paper has brought an unanswered ? from college back to the front of my mind, and I was hoping someone else could help me out.

I understand SAT as a problem and its implications for P/NP. What I'm not clear on, and which my computational complexity professor couldn't/wouldn't elaborate on, is why 3SAT is the "interesting" form of this problem to use?

Conceptually, using clauses makes sense because it allows us to express the logical relationship between literals, but why is it useful to restrict clauses to 3 booleans? Why not 2? Why not 5? What's magic about 3?

[RiderOfGiraffes]

Because 2-SAT is polynomial. 3-SAT is the smallest "interesting" flavor of the SAT family. Limiting the forms makes some sorts of reasoning easier, but 3-SAT and k-SAT are effectively the same. There are simple ways of inter-converting.

ADDED IN EDIT: http://en.wikipedia.org/wiki/2-satisfiability

[bartonfink → RiderOfGiraffes]

Okay - that 2-SAT fact makes sense. Thanks!