by BerislavLopac on 4/17/25, 7:34 AM with 114 comments
by bob1029 on 4/17/25, 9:56 AM
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.
by andrewla on 4/17/25, 1:00 PM
> 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.
by thaumasiotes on 4/17/25, 10:12 AM
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.
by Leszek on 4/17/25, 1:46 PM
by the-grump on 4/17/25, 8:32 AM
That said, you do make a great point OP, and I'll think about it every time the Halting Problem comes up.
by qsort on 4/17/25, 3:02 PM
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.
by ogogmad on 4/17/25, 4:06 PM
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
by chad1n on 4/17/25, 2:43 PM
by waynecochran on 4/17/25, 6:49 PM
by johanvts on 4/17/25, 10:19 AM
Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Maybe this is stating the same?
by ykonstant on 4/17/25, 9:21 AM
by nyrikki on 4/17/25, 4:35 PM
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(∃)
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 [2]https://en.m.wikipedia.org/wiki/List_of_PSPACE-complete_prob... [3]https://en.m.wikipedia.org/wiki/Rice%27s_theorem [4]https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJO...
by graycat on 4/17/25, 8:08 AM
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).
by meindnoch on 4/17/25, 9:34 AM
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)).