Re:Seemingly impossible functional programs (2007)
by Kednicma on Friday July 10, 2020 @08:30PM
(#23798234)
One way to imagine this space is as an indexed bank of light switches. Each switch starts out unset, and our goal is to find a configuration on a finite number of switches which will satisfy our search. The search can only check one switch at a time and must commit after each check. This allows a basic nemesis to compute a configuration by running the search repeatedly and rescuing it after each time it fails by checking the last switch checked.
A gorgeous immediate consequence is that each search is looking for a solution to a SAT problem! Each SAT solution describes the edge of a region of Cantor space whose elements all have the searched-for property. And thus, while the search can proceed in finite time, it must sadly be NP-complete.
A gorgeous immediate consequence is that each search is looking for a solution to a SAT problem! Each SAT solution describes the edge of a region of Cantor space whose elements all have the searched-for property. And thus, while the search can proceed in finite time, it must sadly be NP-complete.