(buttondown.com)

108 points BerislavLopac | 2 comments | 17 Apr 25 07:34 UTC | HN request time: 0.506s | source

1. waynecochran ◴[17 Apr 25 18:49 UTC] No.43720711[source]▶

Halting problem is not even decidable. To mention it in the context of NP is a categorical fouxpas.

2. JohnKemeny ◴[23 Apr 25 21:50 UTC] No.43777002[source]▶

HALT 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.

The Halting Problem is a terrible example of NP-Harder