←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
107 points BerislavLopac | 3 comments | 17 Apr 25 07:34 UTC | HN request time: 0.981s | source
Show context
bob1029 ◴[17 Apr 25 09:56 UTC] No.43714776[source]▶
> Most "definitely harder than NP" problems require a nontrivial background in theoretical computer science or mathematics to understand.

One of the simplest examples of this is automatic program synthesis.

Searching for the optimal (e.g., shortest) program that satisfies a given set of inputs/outputs (function) is an undecidable (worse than exponential time) problem similar to the halting problem. The exponent in this case would have been the size of the instruction set, but we still don't know how many cycles we need (i.e., is it even practical to run?).

In applications like genetic programming, we deal with the halting problem by specifying a maximum # of cycles that the program interpreter will run for each time. The ability of the synthesized programs to halt in a bounded time becomes part of selection pressure. Candidates that return poor or no results within the constraints are quickly eliminated. This can be further compounded by making the candidates evolve their own resource limits as part of their genome.

Put differently, we can approximately solve the halting problem for some smaller problems with clever search techniques. I don't think talking about these things in absolute terms is very useful. Everything depends on the problem and the customer's expectations.

replies(2): >>43714848 #>>43719848 #
pron ◴[17 Apr 25 17:29 UTC] No.43719848[source]▶
I don't know if I would call that "approximately solving the halting problem", and the use of the halting problem is already short-hand for much more general and less binary results. In the 1965 [1] paper by Hartmanis and Stearns that gave birth to computational complexity theory, they generalise the halting theorem to effectively say that it's generally impossible to tell what a program would do (specifically, whether it halts) in it's Nth step without simulating it for N steps. The halting theorem is just the special case where N is any N.

What you're doing isn't approximating or getting around anything. You're simply following the "generalised halting theorem": you're interested in what the program does in N steps, and you're finding that out by simulating it for N steps. You're not making any approximation that shortcuts any computational complexity results. (Such approximations exist in some cases, but that's not what you're doing here)

[1]: On the computational complexity of algorithms: https://www.ams.org/journals/tran/1965-117-00/S0002-9947-196...

replies(1): >>43720560 #
bob1029 ◴[17 Apr 25 18:34 UTC] No.43720560[source]▶
> You're not making any approximation that shortcuts any computational complexity results.

I completely agree in the default/initial case.

> (Such approximations exist in some cases, but that's not what you're doing here)

However, the entire point of genetic programming is that once you find something that is "on the map" at all, you can begin to exploit the region around that program with some reasonably accurate expectations regarding how certain behaviors will unfold in the local space. The larger the population the more stable this tends to become on average.

So, for pure exploration in GP, you do indeed suffer the full weight of the halting theorem. As you transition into the exploitation regime, this becomes more of a grey area.

replies(1): >>43720690 #
pron ◴[17 Apr 25 18:47 UTC] No.43720690[source]▶
> So, for pure exploration in GP, you do indeed suffer the full weight of the halting theorem. As you transition into the exploitation regime, this becomes more of a grey area.

I don't understand what the grey area is. The time hierarchy theorem (that we can consider the "generalised halting theorem") is a theorem; it is absolute. What we have here isn't something that uses some approximation that is true with some probability that we could maybe call a "grey area", but something that bears the full brunt of the theorem.

That there are subsets of problems in some complexity class X that can be solved faster than X's upper limit is the very point of the complexity hierarchy. Yes, there are a subset of problems in EXPTIME that can be solved in polynomial time, hence the existence of the P class, but that doesn't mean that EXPTIME is a "grey area". If you're solving some problem quickly, then we know that what you've solved was not one of the hard problems to begin with. If you're solving some problems in polynomial time, then those problems are in P.

For example, heuristic SAT solvers solve many SAT problems quickly. But their authors don't consider that evidence that P = NP, and understand that the instances that their solvers solve are "easy" (which is not to say they're not useful). In other words, what they're saying is that many useful SAT problems are easy, not that they're able to solve the hard problems efficiently.

replies(2): >>43720988 #>>43728048 #
ComplexSystems ◴[18 Apr 25 13:45 UTC] No.43728048[source]▶
I think the idea in the original post was to adjust the goalposts of the original halting problem to get something easier to solve. Instead of looking for programs that "eventually" halt while reproducing the required outputs, one can look for programs that halt "in some reasonable amount of time." The time-bounded halting problem is easier to solve than the original (it is decidable). As one increases the amount of time one views as "reasonable," one gets a sequence of time-bounded halting problems that can be viewed as successively good approximations of the original. There are many similarly "approximate" or "relaxed" versions of the halting problem that are "good enough" in real life and are perfectly decidable.
replies(1): >>43743049 #
1. pron ◴[20 Apr 25 11:13 UTC] No.43743049[source]▶
Not only is there nothing here that approximates a "solution" to an unsolvable problem, but that there are more programs you can decide the more time you simulate them is the actual statement of generalised halting theorems. Indeed, this is literally how they are summarised: "Informally, these theorems say that given more time, a Turing machine can solve more problems." [1]

When someone says that you can, in practice, sort-of get around the halting theorem by noting you can solve more problems given more time, do you see how it's not an approximation of a "solution" that gets around any theorem but the very point of the theorems? If you see you can solve more things in more time you are observing the halting theorem and its generalisations at work, not getting around them in practice.

But that's not the end of things because now we can ask what it means to "get around" or "approximately get around" a theorem that basically says that you can buy a bike for $50 but you can't buy a car for that price. Saying, "I don't mind riding a bike" is clearly not getting around anything, but saying "most people wouldn't mind riding a bike" could, indeed, be a way to state that the limitations of the theorem don't affect many people in practice. But such a statement also isn't true.

If someone wants to claim that in practice we rarely come across intractability where it matters, that would, indeed, be interesting, but I also don't think it's true. So if someone wants to say that most problems that are interesting in practice are decidable, that may well be true, but even Turing realised that decidability isn't a very interesting property. Decidability was replaced by tractability in the 70s, as halting was replaced by the more general and precise time hierarchy in 1965. We more precisely discovered that not only are there problems that cannot be solved in any time bound, but that there are problems that can be solved in 2^N that cannot be solved in N steps.

And if someone wants to say that we don't frequently come across intractable problems in practice, then that is not true.

If anything, the limits we run across in practice are more constrained than the known theoretical ones. Even though we have yet to prove a hierarchy between P and NP, and even between P and PSPACE, we do find it much harder, in practice, to solve problems that are complete in NP than problems known to be in P, and problems that are complete in PSPACE are harder in practice than those that are complete in NP.

[1]: https://en.wikipedia.org/wiki/Time_hierarchy_theorem

replies(1): >>43764563 #
2. ComplexSystems ◴[22 Apr 25 17:42 UTC] No.43764563[source]▶
The halting problem can be approximated by a sequence of increasingly accurate computable functions - "partial halting oracles" which give the right answer on "many" inputs, with each better than the last.

The sequences "converge to" or "approximate increasingly well" the true halting function in that for any input, there is some point in the sequence such that all subsequent partial halting oracles analyze its behavior correctly.

The halting problem is "unsolvable" because the goalposts are very high. An algorithm to "decide" the halting problem can have no "failure modes" of any kind, even if the probability of failure is vanishingly small. It must work on every single program. As soon as you limit the scope of the programs you care about analyzing in any reasonable way, like "deterministic programs without randomness that use at most 32GB RAM," the proof no longer applies.

The complexity classes you refer to don't conflict with any of this. In the general case, it is undecidable to analyze what complexity class an algorithm (or decision problem) is in, for instance, but this isn't usually summarized as "computational complexity analysis is an unsolvable problem."

replies(1): >>43776589 #
3. pron ◴[23 Apr 25 21:02 UTC] No.43776589[source]▶
My point is that focusing on the halting theorem is silly, because we have much more precise and less binary generalisations of it since 1965. Finding "practical approximations" that are easier than the hard limits is not only not easy, but a huge deal.

> The sequences "converge to" or "approximate increasingly well" the true halting function in that for any input, there is some point in the sequence such that all subsequent partial halting oracles analyze its behavior correctly.

This is irrelevant. It is obviously the case that a "there exists X such that for all Y" is very different from "for all Y there exists X", yet the latter is by no means an "effective approximation" of the former.

At the end of the day, we're always looking for some algorithm that is useful for a large class of inputs, and we know that any such algorithm cannot violate the time hierarchy in any way. It will be able to efficiently solve problems that are easy and unable to efficiently solve problems that are hard. Having any algorithm solve more problems will require it to run longer.

It may be the case that a large set of practical problems are easy, but it is also the case that a large set of practical problems are hard. Only a world-changing discovery such that P = PSPACE or that there are tractable and useful approximations for all of PSPACE will change that.

That doesn't mean, of course, that there may be many interesting easy problems that we're yet to solve.