A Short NP-Completeness Proof
Prove: Waking up is NP-Complete.
Proof:Waking up is NP-Complete iff Waking up is NP-Hard and polynomial-time reducible to CNF.
The lower bound of the most efficient algorithm is 2n and rapidly approaching intractibility. Waking up is NP-Hard.
Every instance of waking up adds a few new cases of whether or not I will actually get out of bed. That is, if those cases can be organized in order to make a Conjunctive-Normal-Form decidability problem. If the cases can be modified to make the full statement true, CNF is satisfied and I will wake up. QED.
1 Comments:
If deciding to get out of bed requires that much complexity, I would say you are already awake anyway.
Post a Comment
<< Home