Timeline for Is boolean validity a harder problem than satisfiability?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 5, 2017 at 18:01 | comment | added | Joey Eremondi | @S.N. Right, but there's an inherent imbalance between YES and NO for how you convert an NTM to DTM. YES requires that there exists a successful execution, whereas NO requires that all halting executions fail. So to prove that an NTM says YES on a given input, you need only provide one trace, but you need to elaborate all traces to prove that it answers NO. In an actual DTM solving SAT you might need to do an exponential number of steps to find an answer if it's YES, but you might get lucky and find one sooner. There's no known way to "get lucky" with NO. | |
| Sep 5, 2017 at 6:26 | comment | added | Motorhead | I'm not sure I completely follow your explanation. What does it mean to say boolean satisfiability is easy for YES and hard for NO. For boolean satisfiability to be NP-complete wouldn't that require that a NDTM be able to answer both YES or NO (as appropriate) in a polynomial number of steps (in the input size)? | |
| Sep 1, 2017 at 20:35 | history | answered | Joey Eremondi | CC BY-SA 3.0 |