4 ms·
Here's how I intuit this: 3-SAT is like "machine language" for other NP problems. Any other NP problem can be "compiled down" to 3-SAT statements. Though it's
by wlievens 16y ago
Here's how I intuit this: 3-SAT is like "machine language" for other NP problems. Any other NP problem can be "compiled down" to 3-SAT statements.
Though it's probably inaccurate, that's how I intuit the matter.
- sid0 16y agoThough it's probably inaccurate, that's how I intuit the matter. It's actually quite accurate, but you can do even better: any other NP problem can be "compiled down" to one 3-SAT statement.
- wlievens 16y agoYou're obvisouly correct. "3-SAT statements" is pretty meaningless in this context since you want to satisfy one big consistent statement.