3 ms·
Halting problem is not even decidable. To mention it in the context of NP is a categorical fouxpas.
by waynecochran 1y ago
Halting problem is not even decidable. To mention it in the context of NP is a categorical fouxpas.
- JohnKemeny 1y agoHALT is a problem that belongs to the complexity class RE (recursively enumerable), which is a class that contains the complexity class NP. NP: Problems with efficient verifiers — given a candidate solution, you can check correctness in polynomial time. RE: Problems with semi-algorithms — you can recognize “yes” instances by eventually halting, but you may run forever on “no” instances. I wouldn't consider it a categorical error.