News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.