7 ms·

The Halting Problem is a terrible example of NP-Harder

108 points by BerislavLopac 2y ago

graycat 2y ago
Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to an earlier state and, thus, be in an infinite loop. So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". Uh, we also assume that before we start, we can look at the design of "the machine" and know how many states there can be and from the speed of the machine how many new states are visited each second. So, we will know how long we have to wait before we see either (a) or (b).
- tgv 2y ago
  Nobody is talking about a finite state machine in complexity. Its time complexity is n, and its space complexity is 0. The Halting Problem specifically pertains to Turing Machines.
  - graycat 2y ago
    What I wrote is correct but does not address the traditional Turing Machine halting problem or solve it. The traditional halting problem is theoretical, i.e., not close to anything practical, and so is what I wrote. And I did not claim that what I wrote is a contribution to "complexity theory". The Turing Machine Halting Problem has long been standard computer science; from that it's common to conclude we can't tell if a program will stop. But that conclusion needs some theoretical assumptions, and my version is simpler and shows that we have to be careful drawing conclusions from the standard treatment.
    - tgv 2y ago
      > What I wrote is correct What your wrote is pretty much trivial, and not related to the topic of the article. It's also not practical, since the space needed to represent even a small program as an FSM is very large. Just try to write an FSM that reads binary coded 16 bit numbers, and has to find the maximum value. Now imagine sorting just 100 of them.
      - graycat 2y ago
        > What your wrote is ... not related to the topic of the article. The article was: The Halting Problem is a terrible example of NP-Harder and I wrote: > So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". > "Trivial"? I never claimed the post was a significant contribution to computer science or complexity theory, and at most only a tiny fraction of posts at HN are such. Also, my post does not address the complexity theory question of P = NP. If what I wrote was "new, correct, and significant", then I should have sent it to a good computer science journal. I've published enough papers in good math and computer science journals to notice that the checks take a long time to arrive. I'm not in academics and never wanted to be. HN is not a journal of new, correct, and significant work in computer science. From responses in this thread, the post has proven to be at least curious and interesting to some of the HN audience.
- brap 2y ago
  But the halting problem is specifically for any kind of program. Otherwise you can just say that every codebase is smaller than X petabytes anyway so it’s always decidable.
  - JohnKemeny 2y ago
    No, the halting problem doesn't hold when you have finite memory (as per OP's point). As OP says, after finitely many iterations (at most 2^n many), you have to be back at a previously seen state, and can terminate.
    - tromp 2y ago
      The halting problem requires both 1) unlimited length of programs whose halting behaviour is to be decided (so it can not be limited to program of at most 10 petabytes) 2) for those programs to have unlimited memory available You're arguing about point 2) in response to a post about point 1).
      - JohnKemeny 2y ago
        Well, the post I responded to was a respons to a post about point 2. I simply reiterated OP's point.
    - chriswarbo 2y ago
      Architectures like x86 can only address a finite amount of RAM, since they have a fixed word size (e.g. 64 bits). However, their memory is still unlimited, since they can read and write to arbitrary IO devices (HDDs, SSDs, S3, etc.); though those operations aren't constant time, they're O(sqrt(n)), since they require more and more layers of indirection (e.g. using an SSD to store the S3 URL of the address of ....)
    - deleted 2y ago
      [deleted]
    - deleted 2y ago
      [deleted]
- Sankozi 2y ago
  Yes, lots of these problems assume fantasy infinite world. Big O notation also suffers from this - it's almost useless for real world problems.
  - suddenlybananas 2y ago
    >Big O notation also suffers from this - it's almost useless for real world problems. It's not the only way to optimize things but there's a reason no one sorts with bubble sort.
    - Sankozi 2y ago
      Yes bubble sort usually will take more time, but big O notation does not say that quick sort will be better for your real world problem. Complexity estimations or just benchmarks are much better at that. You should never limit yourself to big O notation when comparing algorithms.
      - suddenlybananas 2y ago
        >You should never limit yourself to big O notation when comparing algorithms. Sure, but it's still an incredibly useful tool for considering how your algo will scale.
    - LegionMammal978 2y ago
      Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms. In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb.
      - Al-Khwarizmi 2y ago
        Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there.
- Tainnor 2y ago
  This approach suffers from two major problems: * It makes computability and complexity dependent on individual machines (now a program may halt on machine A, but not on machine B). For various reasons, we don't want that. * The entire state space of a single machine consists of all the registers, memory cells, etc. But keeping track of all states that have been visited before requires exponentially more space than the space that is actually available on the machine (because you're computing the powerset). So the machine itself can't solve its halting problem, only a much more powerful one can. Very often, impossibility results in infinitary mathematics translate back to "there's no reasonable way to do this" in actual practice where things are finite.
  - Ukv 2y ago
    You wouldn't necessarily need to keep track of all states that have been visited before, to my understanding, just one extra state that you move along at half the speed (so it'll eventually also enter the loop, and then the state you're progressing at full speed will loop around and hit it). So 2X the memory and 1.5X the time/compute of the program on its own.
    - TheDong 2y ago
      Even simpler, you're just trying to figure out if it halts or not, not the exact length of the cycle, so you can do it with only a single counter for the total number of states. Say you have a machine with 128 bits of state, if it halts in 2^128 (roughly 340 undecillion) steps, that means it halts. If it's still going after 2^128 steps, then it'll keep going forever. So, to see if a 128 bit machine halts, you only need an extra 128 bits to count up 1-by-1 to 2^128. Sure, you also need a few thousand times the lifetime of the known universe just to count that high, but you know, It's O(2^128) instructions which means it's O(1). Good luck doing that on any machine with any real amount of memory of course. Really easy to write "just count to 2^128", but not so easy to do it.
    - Tainnor 2y ago
      This is interesting and I wasn't aware of this algorithm, thanks. I still maintain that it's practically infeasible to exhaust the entire state space of any modern machine.
- userbinator 2y ago
  More information on the algorithm to do so: https://en.wikipedia.org/wiki/Cycle_detection https://en.wikipedia.org/wiki/Cycle_detection
- jerf 2y ago
  That's great and all, but nobody is talking about physical computers here. Moreover, it's a useless observation in practice as well because the full exponentially-large state space necessary to represent such systems is not a useful formalism to approach computers with for any purpose, be it brutally practical or entirely theoretical. See https://news.ycombinator.com/item?id=23431703 https://news.ycombinator.com/item?id=23431703 for some previous comments I made on this, and some rough numbers base on computers that were already small 5 years ago and seem even smaller today. It is not useful to say "hey, that thing you're using has a finite state space and that finite state space is only 10^2,585,827,973 large!" It's not like you're going to run out.
the-grump 2y ago
Technically correct is the best kind of correct, and The Halting Problem is a fun head scratcher for a green computer scientist. I'm glad it was part of my introduction to NP hardness. That said, you do make a great point OP, and I'll think about it every time the Halting Problem comes up.
- edanm 2y ago
  This seems weird to me. I would think the classic way to introduce these topics is to first talk about decidability, introduce the halting problem through that, then introduce complexity. That's certainly how I was introduced to this material. I wouldn't think that you'd learn about the halting problem as only an example of something harder than NP hard.
  - sfink 2y ago
    I agree. NP, NP-complete, and NP-hard are all talking about how long things take. If something is uncomputable, then how long it takes doesn't seem very relevant or interesting. "If Jimmy earns 5 cents a day and a watermelon costs $10, how long will it take for Jimmy to earn enough money to buy the color blue?" Maybe the connection is that it feels like the halting problem could be solved if you had an infinite amount of time?
    - thaumasiotes 2y ago
      The halting problem obviously can be solved if you have an infinite amount of time, as long as terminating is guaranteed to take place within a finite amount of time. If it's possible to terminate after an infinite amount of time, you'll need a more infinite amount of time to check for halting.
ykonstant 2y ago
I am confused about the precise statement of the problem that is claimed to be provably NP-hard, decidable and not in NP. Any clarification?
- penteract 2y ago
  Given a dimension, n; a collection of n-dimensional vectors of integers v_1,..,v_k; and a target n-dimensional vector u: Is there a sequence of vectors from the collection which sums to u, such that no partial sum(of an initial segment of the sequence) has any negative components?
- ngkabra 2y ago
  The article talks about a 2-dimensional grid which starts at (0,0) (bottom right) and extends infinitely to the right and the top, so all (x,y) for non-negative integers x,y exist. But x or y negative does not exist. Given a list of possible jumps e.g. (+1,+10) or (-20,+13), and a target destination, e.g. (700,1). Does there exist a series of valid jumps that takes you from (0,0) to (700,1) without ever going off grid (i.e. into negative territory)? This problem might or might not be NP-Harder. However, now extend the problem to higher dimensional grids. At some number of dimensions, the problem becomes definitely NP-Harder (i.e. NP-hard, decidable, but not in NP)
  - ykonstant 2y ago
    Which number of dimensions, though? Is there an effective bound? Otherwise it is hard to suggest the problem as an example.
    - thaumasiotes 2y ago
      The number of dimensions is one of the variables in the problem.
meindnoch 2y ago
For any function f(n) the problem "compute 2^f(n)" is going to be Ω(f(n)), because the output is f(n) bits; so merely writing down the answer takes Ω(f(n)) steps. Note, that the number n is the input here, which is k = log(n) bits long. So the runtime is actually Ω(f(2^log(n))) = Ω(f(2^k)).
- jhanschoo 2y ago
  This is indeed as trivially true as you say, but this is not a decision problem, which is what the article is discussing. That said, you can use diagonalization over turing machines to construct a language that is indeed strictly more difficult.
- JohnKemeny 2y ago
  Well, since you said "for any function f" ... It's not true for, say, constant functions.
  - meindnoch 2y ago
    How's that so? Calculating 2^C for any fixed C is an asymptotically constant-time operation.
bob1029 2y ago
> 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...
thaumasiotes 2y ago
I agree with the issue ("What's bigger than a dog? THE MOON"), but I don't agree with the need to provide an example that is provably distinct from NP. We're fine providing NP-complete problems without proving that they're distinct from P. There are lots of accessible problems that belong to spaces that probably aren't NP. One that should be familiar to most people studying CS theory is "do these two regular expressions match the same set of strings?". --- For the Diophantine vector reachability problem... I don't really like the Quanta presentation. ("An easy-sounding problem yields numbers too big for our universe.") First, the problem, if you describe it accurately, doesn't sound easy at all. Diophantine problems are never easy. That's why we have real numbers. Second, the article suggests that the problem should be introduced to children by casting in in terms of several rules of exchange ("For Alice, the transition vector (−1, −1, 1, 0) would represent the exchange of an apple and a banana for a cantaloupe."). But that would make the problem trivial: you start at the origin; without a rule of "exchange" in which the other party gives you as much as you want of something for free, you're never going to leave it. And third, many easy problems generate numbers too big for our universe. That's not unusual at all. Compare the question "how many digits of pi do you need before the potential error in calculating the volume of a sphere the size of the visible universe is less than the volume of one hydrogen atom?". Can you imagine using more digits than that? You just involved a number too big for the universe. The article passes over this point itself: > It’s physically impossible to write down all the digits of 2↑↑6 — a liability of living in such a small universe.
- mhink 2y ago
  > Second, the article suggests that the problem should be introduced to children by casting in in terms of several rules of exchange ("For Alice, the transition vector (−1, −1, 1, 0) would represent the exchange of an apple and a banana for a cantaloupe."). But that would make the problem trivial: you start at the origin; without a rule of "exchange" in which the other party gives you as much as you want of something for free, you're never going to leave it. I'm not sure what point you're trying to make here? That specific transition vector would be one such vector among several in a given ruleset. You're correct that for any ruleset, if I don't have at least one vector that can get me away from the origin, I'm stuck there, but then I also have to consider that I still might not be able to get to where I want to go. If I have the ruleset [(2, 0), (-4, 2)] I still can't get to (3, 5).
johanvts 2y ago
> NP-hard is the set all problems at least as hard as NP-complete Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Maybe this is stating the same?
- redleader55 2y ago
  This [1] diagram from Wikipedia represents you are saying in a visual way. NP-hard and NP-complete are defined as basically an equivalence class modulo an algorithm in P which transforms from one problem to the other. In more human terms both NP-hard and NP-complete are reducible with a polynomial algorithm to another problem from their respective class, making them at least as hard. The difference between the two classes, again in human terms, is that NP-complete problems are decision problems "Does X have property Y?", while NP-hard problems can include more types - search problems, optimization, etc, making the class NP-hard strictly larger than NP-complete in set terms. The statement in the article means that NP-hard problems require solving a NP-complete problem plus a P problem - hence being at least as hard. [1] https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-har...
  - zahlman 2y ago
    If NP-hard isn't even a subset of NP, why is it called "NP-hard"?
    - suzumer 2y ago
      Because a language being NP-hard implies it is at least as hard as the hardest NP problems. For any language that is NP-hard, if one had a turing machine that decided the language, one could construct a polynomial time transformation of any language in NP to the NP-hard language to decide it using the NP-hard turing machine.
    - sfink 2y ago
      Membership in NP is a statement about how easy a problem is (specifically, that you can verify an answer in no worse than polynomial time). NP-hard is about how hard a problem is (at a minimum). I wonder if there would be less confusion over this if NP had been called "NP-easy" in the first place. But Wikipedia says that by now that term has already been taken. P is "very easy": you can solve these in polynomial time. NP is "easy": you can verify a solution in polynomial time. Are there any problems you can verify but not solve in polynomial time? Nobody knows! (But ~everyone thinks so.) NP-hard is "hard": it takes polynomial time or more to even verify these.
andrewla 2y ago
The example given doesn't seem right to me. > There is one problem, though, that I find easily explainable. Place a token at the bottom left corner of a grid that extends infinitely up and right, call that point (0, 0). You're given list of valid displacement moves for the token, like (+1, +0), (-20, +13), (-5, -6), etc, and a target point like (700, 1). You may make any sequence of moves in any order, as long as no move ever puts the token off the grid. Does any sequence of moves bring you to the target? If someone gives you such a sequence, it seems trivial to verify it in linear time. Even for arbitrary dimensions, and such witness can be verified in linear time.
- Choco31415 2y ago
  A sequence is easy to verify. Choosing the sequence not so much. Roughly put that is the certificate definition of being in NP.
  - andrewla 2y ago
    The goal here was to show that it was strictly NP-hard, i.e. harder than any problem in NP.
    - Nevermark 2y ago
      Harder to solve, not necessarily harder to verify? If I am understanding things right.
      - andrewla 2y ago
        The crazy thing about the definition of NP-completeness is that Cook's theorem says that all problems in NP can be reduced in polynomial time to an NP-complete problem. So if a witness to a problem can be verified in polynomial time, it is by definition in NP and can be reduced to an NP-complete problem. If I can verify a solution to this problem by finding a path in polynomial time, it is by definition in NP. The goal here was to present an example of a problem known to not be in NP.
Leszek 2y ago
Something I find fascinating is that we know that P != EXPTIME, and that P <= NP <= EXPTIME, but have managed to prove neither P != NP nor NP != EXPTIME. NP has to be somewhere between them but we have no idea where.
- macleginn 2y ago
  "NP has to be somewhere between them but we have no idea where" – I guess that this state of affairs won't change much even if we prove P != NP?
  - dgs_sgd 2y ago
    I think that's unclear. A constructive proof of P != NP might yield insights into the "gap" between them.
nyrikki 2y ago
The problem is that topics like descriptive complexity theory are typically reserved for graduate level courses, and what the author has access to is basically a survey. There are entire hierarchies that describe what is "NP-Harder" specifically the second level of the polynomial hierarchy, where NP == Σ_1^p IMHO one of the most useful parts of the -complete concepts is as a meet-me where one can find possible reductions that may work in your use case, but even with just P and NP you can find useful mappings like: P = FO(LFP)=FO(n^O(1))=SO(Horn) NP = PCP(0,poly(n)) = PCP(log n, log n) = PCP(log n, 1) = Σ^1 = SO(∃) There are entire hierarchies that describe what is "NP-Harder" specifically the second level of the polynomial hierarchy, where NP == Σ_1^p The arithmetic and exponential hierarchies, which the author mentions are actually nearly just as big as a jump to HALT from the polynomial hierarchy. The reason that PSPACE is invoked (class of decision problems solvable by a Turing machine in polynomial space). Is because is because PSPACE contains PH, the Polynomial-Time Hierarchy[1] which is what the author seems to have been looking for. The PSPACE-complete problems[2] are also a great meet-me space for either looking for some special case reduction, or understanding that complexity from your preferred abstract model. As space* is always more valuable then time, because you have to read, which takes time, it is common to have that transition. But then things get crazy too. HALT and NP are very closely related in a practical method because of the Entscheidungsproblem, which is the decision problem issue. But you have to think in the General case, not a restricted problem. You can verify any NP problem in poly time, just as you can tell that a machine halts, but you cannot pre-guess that. A possibly useful lens for this is the generalization of HALT, Rice's Theorem[3] > Rice's theorem states that all non-trivial semantic properties of programs are undecidable. > Given a program P which takes a natural number n and returns a natural number P(n), the following questions are undecidable: * Does P terminate on a given n? (This is the halting problem.) * Does P terminate on 0? * Does P terminate on all n (i.e., is P total)? * Does P terminate and return 0 on every input? * Does P terminate and return 0 on some input? * Does P terminate and return the same value for all inputs? * Is P equivalent to a given program Q? If you quit thinking about NP as something that can be brute forced, as yes NP can be simulated on a TM, and think about a decider program running and deciding without running the actual program this will help connect the dots. Understanding that this decision has to happen without access to the semantic properties (runtime behavior) but only has access to the syntax of a program will open lots of concepts for you. If moving past the oversimplified "survey" level explanations is of interest there are many resources, but here is one play list that some trusted people I know claimed was useful[4]. One of the more common descriptive complexity books is "Descriptive Complexity" by Neil Immerman, and even complexityzoo references[1] can help. To be clear, I can understand why these oversimplified introduction explanations can be frustrating, and the curriculum could and should be improved. [1]https://complexityzoo.net/Complexity_Zoo:P#ph https://complexityzoo.net/Complexity_Zoo:P#ph [2]https://en.m.wikipedia.org/wiki/List_of_PSPACE-complete_problems https://en.m.wikipedia.org/wiki/List_of_PSPACE-complete_prob... [3]https://en.m.wikipedia.org/wiki/Rice%27s_theorem https://en.m.wikipedia.org/wiki/Rice%27s_theorem [4]https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJOzYNsaXYLAOKH https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJO...
chad1n 2y ago
To be honest, checking if there is a path between two nodes is a better example of NP-Hard, because it's obvious why you can't verify a solution in polynomial time. Sure the problem isn't decidable, but it's hard to give problems are decidable and explain why the proof can't be verified in P time. Only problems that involve playing optimally a game (with more than one player) that can have cycles come to mind. These are the "easiest" to grasp.
- nmilo 2y ago
  Isn't this NP-complete? The "solution" here would be the steps to take in the path which can be found by brute-force Wikipedia: > 2. When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. > 3. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.
qsort 2y ago
The million dollar question here is... a literal million dollar question. The natural way to go up in complexity from NP is along the polynomial hierarchy, but since it could be the case that P=NP, those problems aren't provably harder.For all we know it could even be the case that P=PSPACE. You could invoke the nondeterministic variant of the time-hierarchy theorem.
ogogmad 2y ago
Is the problem mentioned in the article equivalent to deciding whether there exists a solution to a system of linear equations in the positive integers? I think no, because the vector additions are considered in sequence, and at no point are you allowed to leave the positive quadrant. [Edit] Yeah, it's more than just solving positive integer linear systems: https://en.m.wikipedia.org/wiki/Vector_addition_system https://en.m.wikipedia.org/wiki/Vector_addition_system
- hwayne 2y ago
  IIRC without that restriction the problem is "just" NP-complete.
curtisszmania 2y ago
[dead]
waynecochran 2y ago
Halting problem is not even decidable. To mention it in the context of NP is a categorical fouxpas.
- JohnKemeny 1y ago
  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.
deleted 2y ago
[deleted]

108 points by BerislavLopac 2y ago

Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to an earlier state and, thus, be in an infinite loop. So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". Uh, we also assume that before we start, we can look at the design of "the machine" and know how many states there can be and from the speed of the machine how many new states are visited each second. So, we will know how long we have to wait before we see either (a) or (b).

tgv 2y ago
Nobody is talking about a finite state machine in complexity. Its time complexity is n, and its space complexity is 0. The Halting Problem specifically pertains to Turing Machines.
- graycat 2y ago
  What I wrote is correct but does not address the traditional Turing Machine halting problem or solve it. The traditional halting problem is theoretical, i.e., not close to anything practical, and so is what I wrote. And I did not claim that what I wrote is a contribution to "complexity theory". The Turing Machine Halting Problem has long been standard computer science; from that it's common to conclude we can't tell if a program will stop. But that conclusion needs some theoretical assumptions, and my version is simpler and shows that we have to be careful drawing conclusions from the standard treatment.
  - tgv 2y ago
    > What I wrote is correct What your wrote is pretty much trivial, and not related to the topic of the article. It's also not practical, since the space needed to represent even a small program as an FSM is very large. Just try to write an FSM that reads binary coded 16 bit numbers, and has to find the maximum value. Now imagine sorting just 100 of them.
    - graycat 2y ago
      > What your wrote is ... not related to the topic of the article. The article was: The Halting Problem is a terrible example of NP-Harder and I wrote: > So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". > "Trivial"? I never claimed the post was a significant contribution to computer science or complexity theory, and at most only a tiny fraction of posts at HN are such. Also, my post does not address the complexity theory question of P = NP. If what I wrote was "new, correct, and significant", then I should have sent it to a good computer science journal. I've published enough papers in good math and computer science journals to notice that the checks take a long time to arrive. I'm not in academics and never wanted to be. HN is not a journal of new, correct, and significant work in computer science. From responses in this thread, the post has proven to be at least curious and interesting to some of the HN audience.
brap 2y ago
But the halting problem is specifically for any kind of program. Otherwise you can just say that every codebase is smaller than X petabytes anyway so it’s always decidable.
- JohnKemeny 2y ago
  No, the halting problem doesn't hold when you have finite memory (as per OP's point). As OP says, after finitely many iterations (at most 2^n many), you have to be back at a previously seen state, and can terminate.
  - tromp 2y ago
    The halting problem requires both 1) unlimited length of programs whose halting behaviour is to be decided (so it can not be limited to program of at most 10 petabytes) 2) for those programs to have unlimited memory available You're arguing about point 2) in response to a post about point 1).
    - JohnKemeny 2y ago
      Well, the post I responded to was a respons to a post about point 2. I simply reiterated OP's point.
  - chriswarbo 2y ago
    Architectures like x86 can only address a finite amount of RAM, since they have a fixed word size (e.g. 64 bits). However, their memory is still unlimited, since they can read and write to arbitrary IO devices (HDDs, SSDs, S3, etc.); though those operations aren't constant time, they're O(sqrt(n)), since they require more and more layers of indirection (e.g. using an SSD to store the S3 URL of the address of ....)
  - deleted 2y ago
    [deleted]
  - deleted 2y ago
    [deleted]
Sankozi 2y ago
Yes, lots of these problems assume fantasy infinite world. Big O notation also suffers from this - it's almost useless for real world problems.
- suddenlybananas 2y ago
  >Big O notation also suffers from this - it's almost useless for real world problems. It's not the only way to optimize things but there's a reason no one sorts with bubble sort.
  - Sankozi 2y ago
    Yes bubble sort usually will take more time, but big O notation does not say that quick sort will be better for your real world problem. Complexity estimations or just benchmarks are much better at that. You should never limit yourself to big O notation when comparing algorithms.
    - suddenlybananas 2y ago
      >You should never limit yourself to big O notation when comparing algorithms. Sure, but it's still an incredibly useful tool for considering how your algo will scale.
  - LegionMammal978 2y ago
    Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms. In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb.
    - Al-Khwarizmi 2y ago
      Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there.
Tainnor 2y ago
This approach suffers from two major problems: * It makes computability and complexity dependent on individual machines (now a program may halt on machine A, but not on machine B). For various reasons, we don't want that. * The entire state space of a single machine consists of all the registers, memory cells, etc. But keeping track of all states that have been visited before requires exponentially more space than the space that is actually available on the machine (because you're computing the powerset). So the machine itself can't solve its halting problem, only a much more powerful one can. Very often, impossibility results in infinitary mathematics translate back to "there's no reasonable way to do this" in actual practice where things are finite.
- Ukv 2y ago
  You wouldn't necessarily need to keep track of all states that have been visited before, to my understanding, just one extra state that you move along at half the speed (so it'll eventually also enter the loop, and then the state you're progressing at full speed will loop around and hit it). So 2X the memory and 1.5X the time/compute of the program on its own.
  - TheDong 2y ago
    Even simpler, you're just trying to figure out if it halts or not, not the exact length of the cycle, so you can do it with only a single counter for the total number of states. Say you have a machine with 128 bits of state, if it halts in 2^128 (roughly 340 undecillion) steps, that means it halts. If it's still going after 2^128 steps, then it'll keep going forever. So, to see if a 128 bit machine halts, you only need an extra 128 bits to count up 1-by-1 to 2^128. Sure, you also need a few thousand times the lifetime of the known universe just to count that high, but you know, It's O(2^128) instructions which means it's O(1). Good luck doing that on any machine with any real amount of memory of course. Really easy to write "just count to 2^128", but not so easy to do it.
  - Tainnor 2y ago
    This is interesting and I wasn't aware of this algorithm, thanks. I still maintain that it's practically infeasible to exhaust the entire state space of any modern machine.
userbinator 2y ago
More information on the algorithm to do so: https://en.wikipedia.org/wiki/Cycle_detection https://en.wikipedia.org/wiki/Cycle_detection
jerf 2y ago
That's great and all, but nobody is talking about physical computers here. Moreover, it's a useless observation in practice as well because the full exponentially-large state space necessary to represent such systems is not a useful formalism to approach computers with for any purpose, be it brutally practical or entirely theoretical. See https://news.ycombinator.com/item?id=23431703 https://news.ycombinator.com/item?id=23431703 for some previous comments I made on this, and some rough numbers base on computers that were already small 5 years ago and seem even smaller today. It is not useful to say "hey, that thing you're using has a finite state space and that finite state space is only 10^2,585,827,973 large!" It's not like you're going to run out.

the-grump 2y ago

Technically correct is the best kind of correct, and The Halting Problem is a fun head scratcher for a green computer scientist. I'm glad it was part of my introduction to NP hardness. That said, you do make a great point OP, and I'll think about it every time the Halting Problem comes up.

edanm 2y ago
This seems weird to me. I would think the classic way to introduce these topics is to first talk about decidability, introduce the halting problem through that, then introduce complexity. That's certainly how I was introduced to this material. I wouldn't think that you'd learn about the halting problem as only an example of something harder than NP hard.
- sfink 2y ago
  I agree. NP, NP-complete, and NP-hard are all talking about how long things take. If something is uncomputable, then how long it takes doesn't seem very relevant or interesting. "If Jimmy earns 5 cents a day and a watermelon costs $10, how long will it take for Jimmy to earn enough money to buy the color blue?" Maybe the connection is that it feels like the halting problem could be solved if you had an infinite amount of time?
  - thaumasiotes 2y ago
    The halting problem obviously can be solved if you have an infinite amount of time, as long as terminating is guaranteed to take place within a finite amount of time. If it's possible to terminate after an infinite amount of time, you'll need a more infinite amount of time to check for halting.

ykonstant 2y ago

I am confused about the precise statement of the problem that is claimed to be provably NP-hard, decidable and not in NP. Any clarification?

penteract 2y ago
Given a dimension, n; a collection of n-dimensional vectors of integers v_1,..,v_k; and a target n-dimensional vector u: Is there a sequence of vectors from the collection which sums to u, such that no partial sum(of an initial segment of the sequence) has any negative components?
ngkabra 2y ago
The article talks about a 2-dimensional grid which starts at (0,0) (bottom right) and extends infinitely to the right and the top, so all (x,y) for non-negative integers x,y exist. But x or y negative does not exist. Given a list of possible jumps e.g. (+1,+10) or (-20,+13), and a target destination, e.g. (700,1). Does there exist a series of valid jumps that takes you from (0,0) to (700,1) without ever going off grid (i.e. into negative territory)? This problem might or might not be NP-Harder. However, now extend the problem to higher dimensional grids. At some number of dimensions, the problem becomes definitely NP-Harder (i.e. NP-hard, decidable, but not in NP)
- ykonstant 2y ago
  Which number of dimensions, though? Is there an effective bound? Otherwise it is hard to suggest the problem as an example.
  - thaumasiotes 2y ago
    The number of dimensions is one of the variables in the problem.

meindnoch 2y ago

For any function f(n) the problem "compute 2^f(n)" is going to be Ω(f(n)), because the output is f(n) bits; so merely writing down the answer takes Ω(f(n)) steps. Note, that the number n is the input here, which is k = log(n) bits long. So the runtime is actually Ω(f(2^log(n))) = Ω(f(2^k)).

jhanschoo 2y ago
This is indeed as trivially true as you say, but this is not a decision problem, which is what the article is discussing. That said, you can use diagonalization over turing machines to construct a language that is indeed strictly more difficult.
JohnKemeny 2y ago
Well, since you said "for any function f" ... It's not true for, say, constant functions.
- meindnoch 2y ago
  How's that so? Calculating 2^C for any fixed C is an asymptotically constant-time operation.

bob1029 2y ago

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

thaumasiotes 2y ago

I agree with the issue ("What's bigger than a dog? THE MOON"), but I don't agree with the need to provide an example that is provably distinct from NP. We're fine providing NP-complete problems without proving that they're distinct from P. There are lots of accessible problems that belong to spaces that probably aren't NP. One that should be familiar to most people studying CS theory is "do these two regular expressions match the same set of strings?". --- For the Diophantine vector reachability problem... I don't really like the Quanta presentation. ("An easy-sounding problem yields numbers too big for our universe.") First, the problem, if you describe it accurately, doesn't sound easy at all. Diophantine problems are never easy. That's why we have real numbers. Second, the article suggests that the problem should be introduced to children by casting in in terms of several rules of exchange ("For Alice, the transition vector (−1, −1, 1, 0) would represent the exchange of an apple and a banana for a cantaloupe."). But that would make the problem trivial: you start at the origin; without a rule of "exchange" in which the other party gives you as much as you want of something for free, you're never going to leave it. And third, many easy problems generate numbers too big for our universe. That's not unusual at all. Compare the question "how many digits of pi do you need before the potential error in calculating the volume of a sphere the size of the visible universe is less than the volume of one hydrogen atom?". Can you imagine using more digits than that? You just involved a number too big for the universe. The article passes over this point itself: > It’s physically impossible to write down all the digits of 2↑↑6 — a liability of living in such a small universe.

mhink 2y ago
> Second, the article suggests that the problem should be introduced to children by casting in in terms of several rules of exchange ("For Alice, the transition vector (−1, −1, 1, 0) would represent the exchange of an apple and a banana for a cantaloupe."). But that would make the problem trivial: you start at the origin; without a rule of "exchange" in which the other party gives you as much as you want of something for free, you're never going to leave it. I'm not sure what point you're trying to make here? That specific transition vector would be one such vector among several in a given ruleset. You're correct that for any ruleset, if I don't have at least one vector that can get me away from the origin, I'm stuck there, but then I also have to consider that I still might not be able to get to where I want to go. If I have the ruleset [(2, 0), (-4, 2)] I still can't get to (3, 5).

johanvts 2y ago

> NP-hard is the set all problems at least as hard as NP-complete Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Maybe this is stating the same?

redleader55 2y ago
This [1] diagram from Wikipedia represents you are saying in a visual way. NP-hard and NP-complete are defined as basically an equivalence class modulo an algorithm in P which transforms from one problem to the other. In more human terms both NP-hard and NP-complete are reducible with a polynomial algorithm to another problem from their respective class, making them at least as hard. The difference between the two classes, again in human terms, is that NP-complete problems are decision problems "Does X have property Y?", while NP-hard problems can include more types - search problems, optimization, etc, making the class NP-hard strictly larger than NP-complete in set terms. The statement in the article means that NP-hard problems require solving a NP-complete problem plus a P problem - hence being at least as hard. [1] https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-har...
- zahlman 2y ago
  If NP-hard isn't even a subset of NP, why is it called "NP-hard"?
  - suzumer 2y ago
    Because a language being NP-hard implies it is at least as hard as the hardest NP problems. For any language that is NP-hard, if one had a turing machine that decided the language, one could construct a polynomial time transformation of any language in NP to the NP-hard language to decide it using the NP-hard turing machine.
  - sfink 2y ago
    Membership in NP is a statement about how easy a problem is (specifically, that you can verify an answer in no worse than polynomial time). NP-hard is about how hard a problem is (at a minimum). I wonder if there would be less confusion over this if NP had been called "NP-easy" in the first place. But Wikipedia says that by now that term has already been taken. P is "very easy": you can solve these in polynomial time. NP is "easy": you can verify a solution in polynomial time. Are there any problems you can verify but not solve in polynomial time? Nobody knows! (But ~everyone thinks so.) NP-hard is "hard": it takes polynomial time or more to even verify these.

andrewla 2y ago

The example given doesn't seem right to me. > There is one problem, though, that I find easily explainable. Place a token at the bottom left corner of a grid that extends infinitely up and right, call that point (0, 0). You're given list of valid displacement moves for the token, like (+1, +0), (-20, +13), (-5, -6), etc, and a target point like (700, 1). You may make any sequence of moves in any order, as long as no move ever puts the token off the grid. Does any sequence of moves bring you to the target? If someone gives you such a sequence, it seems trivial to verify it in linear time. Even for arbitrary dimensions, and such witness can be verified in linear time.

Choco31415 2y ago
A sequence is easy to verify. Choosing the sequence not so much. Roughly put that is the certificate definition of being in NP.
- andrewla 2y ago
  The goal here was to show that it was strictly NP-hard, i.e. harder than any problem in NP.
  - Nevermark 2y ago
    Harder to solve, not necessarily harder to verify? If I am understanding things right.
    - andrewla 2y ago
      The crazy thing about the definition of NP-completeness is that Cook's theorem says that all problems in NP can be reduced in polynomial time to an NP-complete problem. So if a witness to a problem can be verified in polynomial time, it is by definition in NP and can be reduced to an NP-complete problem. If I can verify a solution to this problem by finding a path in polynomial time, it is by definition in NP. The goal here was to present an example of a problem known to not be in NP.

Leszek 2y ago

Something I find fascinating is that we know that P != EXPTIME, and that P <= NP <= EXPTIME, but have managed to prove neither P != NP nor NP != EXPTIME. NP has to be somewhere between them but we have no idea where.

macleginn 2y ago
"NP has to be somewhere between them but we have no idea where" – I guess that this state of affairs won't change much even if we prove P != NP?
- dgs_sgd 2y ago
  I think that's unclear. A constructive proof of P != NP might yield insights into the "gap" between them.

nyrikki 2y ago

The problem is that topics like descriptive complexity theory are typically reserved for graduate level courses, and what the author has access to is basically a survey. There are entire hierarchies that describe what is "NP-Harder" specifically the second level of the polynomial hierarchy, where NP == Σ_1^p IMHO one of the most useful parts of the -complete concepts is as a meet-me where one can find possible reductions that may work in your use case, but even with just P and NP you can find useful mappings like: P = FO(LFP)=FO(n^O(1))=SO(Horn) NP = PCP(0,poly(n)) = PCP(log n, log n) = PCP(log n, 1) = Σ^1 = SO(∃) There are entire hierarchies that describe what is "NP-Harder" specifically the second level of the polynomial hierarchy, where NP == Σ_1^p The arithmetic and exponential hierarchies, which the author mentions are actually nearly just as big as a jump to HALT from the polynomial hierarchy. The reason that PSPACE is invoked (class of decision problems solvable by a Turing machine in polynomial space). Is because is because PSPACE contains PH, the Polynomial-Time Hierarchy[1] which is what the author seems to have been looking for. The PSPACE-complete problems[2] are also a great meet-me space for either looking for some special case reduction, or understanding that complexity from your preferred abstract model. As space* is always more valuable then time, because you have to read, which takes time, it is common to have that transition. But then things get crazy too. HALT and NP are very closely related in a practical method because of the Entscheidungsproblem, which is the decision problem issue. But you have to think in the General case, not a restricted problem. You can verify any NP problem in poly time, just as you can tell that a machine halts, but you cannot pre-guess that. A possibly useful lens for this is the generalization of HALT, Rice's Theorem[3] > Rice's theorem states that all non-trivial semantic properties of programs are undecidable. > Given a program P which takes a natural number n and returns a natural number P(n), the following questions are undecidable: * Does P terminate on a given n? (This is the halting problem.) * Does P terminate on 0? * Does P terminate on all n (i.e., is P total)? * Does P terminate and return 0 on every input? * Does P terminate and return 0 on some input? * Does P terminate and return the same value for all inputs? * Is P equivalent to a given program Q? If you quit thinking about NP as something that can be brute forced, as yes NP can be simulated on a TM, and think about a decider program running and deciding without running the actual program this will help connect the dots. Understanding that this decision has to happen without access to the semantic properties (runtime behavior) but only has access to the syntax of a program will open lots of concepts for you. If moving past the oversimplified "survey" level explanations is of interest there are many resources, but here is one play list that some trusted people I know claimed was useful[4]. One of the more common descriptive complexity books is "Descriptive Complexity" by Neil Immerman, and even complexityzoo references[1] can help. To be clear, I can understand why these oversimplified introduction explanations can be frustrating, and the curriculum could and should be improved. [1]https://complexityzoo.net/Complexity_Zoo:P#ph https://complexityzoo.net/Complexity_Zoo:P#ph [2]https://en.m.wikipedia.org/wiki/List_of_PSPACE-complete_problems https://en.m.wikipedia.org/wiki/List_of_PSPACE-complete_prob... [3]https://en.m.wikipedia.org/wiki/Rice%27s_theorem https://en.m.wikipedia.org/wiki/Rice%27s_theorem [4]https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJOzYNsaXYLAOKH https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJO...

chad1n 2y ago

To be honest, checking if there is a path between two nodes is a better example of NP-Hard, because it's obvious why you can't verify a solution in polynomial time. Sure the problem isn't decidable, but it's hard to give problems are decidable and explain why the proof can't be verified in P time. Only problems that involve playing optimally a game (with more than one player) that can have cycles come to mind. These are the "easiest" to grasp.

nmilo 2y ago
Isn't this NP-complete? The "solution" here would be the steps to take in the path which can be found by brute-force Wikipedia: > 2. When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. > 3. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.

qsort 2y ago

The million dollar question here is... a literal million dollar question. The natural way to go up in complexity from NP is along the polynomial hierarchy, but since it could be the case that P=NP, those problems aren't provably harder.For all we know it could even be the case that P=PSPACE. You could invoke the nondeterministic variant of the time-hierarchy theorem.

ogogmad 2y ago

Is the problem mentioned in the article equivalent to deciding whether there exists a solution to a system of linear equations in the positive integers? I think no, because the vector additions are considered in sequence, and at no point are you allowed to leave the positive quadrant. [Edit] Yeah, it's more than just solving positive integer linear systems: https://en.m.wikipedia.org/wiki/Vector_addition_system https://en.m.wikipedia.org/wiki/Vector_addition_system

hwayne 2y ago
IIRC without that restriction the problem is "just" NP-complete.

curtisszmania 2y ago

[dead]

waynecochran 2y ago

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

JohnKemeny 1y ago
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.

deleted 2y ago

[deleted]