The Halting Problem is a terrible example of NP-Harder

108 点作者 BerislavLopac27 天前

14 条评论

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

评论 #43719848 未加载

评论 #43714848 未加载

andrewla27 天前

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.

评论 #43717130 未加载

评论 #43716408 未加载

评论 #43716238 未加载

评论 #43716279 未加载

thaumasiotes27 天前

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.

评论 #43723194 未加载

Leszek27 天前

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.

评论 #43718347 未加载

the-grump27 天前

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.

评论 #43715688 未加载

qsort26 天前

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.

ogogmad26 天前

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: <a href="https://en.m.wikipedia.org/wiki/Vector_addition_system" rel="nofollow">https://en.m.wikipedia.org/wiki/Vector_addition_system</a>

评论 #43720871 未加载

chad1n26 天前

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.

评论 #43718786 未加载

waynecochran26 天前

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

评论 #43777002 未加载

johanvts27 天前

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

评论 #43716558 未加载

评论 #43715007 未加载

ykonstant27 天前

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?

评论 #43714727 未加载

评论 #43714692 未加载

nyrikki26 天前

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^pIMHO 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:<pre><code> 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(∃) </code></pre> There are entire hierarchies that describe what is "NP-Harder" specifically the second level of the polynomial hierarchy, where NP == Σ_1^pThe 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]<a href="https://complexityzoo.net/Complexity_Zoo:P#ph" rel="nofollow">https://complexityzoo.net/Complexity_Zoo:P#ph</a> [2]<a href="https://en.m.wikipedia.org/wiki/List_of_PSPACE-complete_problems" rel="nofollow">https://en.m.wikipedia.org/wiki/List_of_PSPACE-complete_prob...</a> [3]<a href="https://en.m.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow">https://en.m.wikipedia.org/wiki/Rice%27s_theorem</a> [4]<a href="https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJOzYNsaXYLAOKH" rel="nofollow">https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJO...</a>

graycat27 天前

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

评论 #43714742 未加载

评论 #43714273 未加载

评论 #43714402 未加载

评论 #43717019 未加载

评论 #43714513 未加载

评论 #43714285 未加载

meindnoch27 天前

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

评论 #43714700 未加载

评论 #43717124 未加载