4 ms·

> Most "definitely harder than NP" problems require a nontrivial background in theoretical computer science or mathematics to understand. One of the simplest e

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

frontfor 2y ago
> I don't think talking about these things in absolute terms is very useful. Everything depends on the problem and the customer's expectations. Agreed. In the real world, approximate solutions to hard problems are often good enough. For instance, the TSP might be a hard problem, but solving it exactly is pointless since the distances between nodes might be subject to measurement uncertainty anyway, and actual travel times might not be fixed as they might fall under a distribution. Having said that, it’s still worth studying the theoretical aspects of these problems.
pron 2y ago
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-1965-0170805-7/S0002-9947-1965-0170805-7.pdf https://www.ams.org/journals/tran/1965-117-00/S0002-9947-196...
- bob1029 2y ago
  > 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.
  - pron 2y ago
    > 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.
    - hwayne 2y ago
      > 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. I thought complexity classes applied to the problem definition, not the specific instances of the problem? An easy SAT problem instance doesn't belong in any complexity class, the set of SAT problem instances belongs to NP.

frontfor 2y ago

> I don't think talking about these things in absolute terms is very useful. Everything depends on the problem and the customer's expectations. Agreed. In the real world, approximate solutions to hard problems are often good enough. For instance, the TSP might be a hard problem, but solving it exactly is pointless since the distances between nodes might be subject to measurement uncertainty anyway, and actual travel times might not be fixed as they might fall under a distribution. Having said that, it’s still worth studying the theoretical aspects of these problems.

pron 2y ago

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-1965-0170805-7/S0002-9947-1965-0170805-7.pdf https://www.ams.org/journals/tran/1965-117-00/S0002-9947-196...

bob1029 2y ago
> 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.
- pron 2y ago
  > 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.
  - hwayne 2y ago
    > 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. I thought complexity classes applied to the problem definition, not the specific instances of the problem? An easy SAT problem instance doesn't belong in any complexity class, the set of SAT problem instances belongs to NP.