-1

According to Gödel's incompleteness theorem, not every problem can be solved using algorithms. How do we know if a problem can be solved using algorithm?
How do we know that NP problems are algorithmically solvable?

closed as unclear what you're asking by kevin cline, Thomas Junk, durron597, user40980, user22815 Oct 19 '15 at 14:52

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • Aren't NP problems solveable by definition? – Ben Aaronson Oct 17 '15 at 9:22
  • I believe this would be a duplicate on CS.SE of Why decision problem definition ignores Gödel incompleteness theorem? – user40980 Oct 18 '15 at 0:19
  • @MichaelT: So you understand that other question? I find it completely incomprehensible and can't see much of a connection. – user144228 Oct 18 '15 at 10:26
  • @HansAdler it has been many years since I had to delve into the intersection of philosophy and computer science. That question and answer appear to try to answer it, though I would have to dust off a fair amount of my old text books to get back up to the point of being able to have the necessary background to say so with certainty. My connection was based on set of tags and the nature of this being a decision problem. – user40980 Oct 19 '15 at 2:58
3

Equivalence of Gödel's incompleteness theorem and the halting problem

Proving undecidability of the halting problem and deducing Gödel's first incompleteness theorem from it is actually in many ways the best approach when giving a class in which one introduces (or can assume) both first-order logic and computability. I think it's both faster this way and easier to understand. Therefore it seems rather pointless to prove the halting problem via Gödel's incompleteness theorem, but it can be done.

Proof sketch:

Suppose the halting problem is decidable. We will construct a counter-example to Gödel's theorem, i.e. a complete recursive extension of Peano Arithmetic.

Peano Arithmetic is of course incomplete, but it is recursive (i.e. the set of its axioms is recursive=computable), and so the set of all consequences of Peano Arithmetic is recursively=computably enumerable and therefore (given that the halting problem is decidable) computable.

Using some natural enumeration of all sentences of the language of Peano Arithmetic, we can take the smallest sentence φ such that neither φ nor its negation ¬φ is a consequence of the axioms. We then add φ to the axioms. (Or ¬φ. It doesn't matter because the result will be consistent either way.) With one more axiom we have more consequences. If the theory is still not complete, we can take the sentence that is now the smallest one such that neither itself nor its negation follows from the (new) axioms, and add this sentence to the axioms. And so on.

The process will either stop when we have found a completion by adding finitely many sentences, or we will have to add infinitely many sentences. But even then it's easy to see that the resulting theory is complete.

But is it still recursive? Yes, provided that we could find each minimal φ that was independent of the previous axioms by using an algorithm (and always the same one). Checking this is where the real difficulty of the proof lies, but it should be rather straightforward.

Though not as straightforward as proving the undecidability of the halting problem directly. ☐

Impact of the halting problem on real-life computing

Yes, this is a real problem. Deciding whether an arbitrary given computer program will halt is a key problem for which we would love to have an algorithm. It's unfortunate that none can exist.

If the halting problem were decidable (and there were no feasibility issues), then this would no doubt change the practical aspects of computing significantly. Even today there exist compilers that reject programs which won't halt on every possible input. The problem is that these compilers cannot work perfectly and have to approximate. One option is for them to try proving that for some input the program doesn't halt, and to accept every program for which they can't find a problem. In practice this can work quite well, catching most programmer errors that lead to infinite loops; but there is no absolute guarantee. The other option is for them to try proving that the program halts for every input, and reject a program if they can't prove it. The problem with this is that such compilers will always reject some programs that do actually halt on every input. And this is not just an issue of rewriting the program differently: It can be proved that no matter how good the heuristics of such a compiler, there will always be computable problems for which it doesn't accept any algorithm at all.

A corollary of the undecidability of the halting problem is the fact that you cannot decide whether a complicated system for synchronisation between threads or processes is OK, or whether deadlocks can occur. Each time you are faced with a frozen application window, you can blame undecidability of the halting problem.

How do we know if a problem has an algorithm?

We know there is an algorithm, when we have found an algorithm. Basically it's as easy as this. And we know that there is no algorithm if we can prove that such an algorithm would lead to a mathematical contradiction. The typical way that one proves there is no algorithm for a problem is by showing that such an algorithm could be used to decide the halting problem.

Theoretically this leaves a class of problems for which we can neither provide an algorithm (yet?) nor prove non-existence of an algorithm (yet?). I think in practice this has never happened so far. I think such problems are known to exist, but it seems likely that they are all so weird that humans simply have no use for any of them. Yet. This may change at some point in the future as we learn to ask our computers more sophisticated questions.

How do we know that NP problems have algorithms?

This is easy. We know this because it's part of the definition. By "NP problem" you may have meant "NP-complete problem", but even this doesn't make a difference because it means belonging to the hardest class of NP problems. So let's look at how NP is defined.

A problem is in P if there exists an algorithm for it which gives the correct solution for every input in time that is bounded from above by a polynomial of the input length. This class of problems is interesting because it's easy to handle in the theory and we found that in practice the coefficients and exponents of the polynomials usually don't get too big. (There are exceptions. E.g., there is an algorithm for tree-decompositions of graphs that runs in linear time but is completely useless in practice because the coefficient is enormous.)

A problem is in NP if there is a non-deterministic algorithm (i.e. sometimes branching or not based on coin throws) which for every single input has a chance to find the correct solution in time bounded by a polynomial in the input, but if it isn't lucky may run forever. It is easy to see how to turn this into an algorithm that tries out all possibilities until it stops with the correct solution after time at most exponential in the input length. (Hint: breadth-first search among the possible coin throw sequences.) So every NP problem has an exponential algorithm, and thus in particular an algorithm.

Almost all problems of practical importance are not just decidable, they are in fact in NP. If the question whether P=NP should ever get a positive solution, this would either provide us with faster algorithms for a lot of problems, or with a lot of additional examples showing that the polynomials needed for a problem in P can be so unwieldy as to be useless in practice.

Note on spelling

Please, please, please don't just drop the two dots off German umlauts. Accents in French, Spanish, Italian and many other languages were added at some point to make certain words distinguishable or give pronunciation hints. But the two dots in German are originally abbreviations for an e following the base letter. You don't have to use umlauts in English, but if you don't you must use the e like this: Goedel. Otherwise it's not just poor typography, it's a spelling mistake. (Yes, even in English. Only poorly edited English-speaking media such as parts of the sports press get this wrong.)

5

According to Godel's incompleteness theorem, not every problem can be solved using algorithms.

That is incorrect, according to my understanding. Godel's incompleteness theorems are not about algorithms. They are actually about whether all mathematical statements can be proved or disproved.

(Godel's first theorem says that there is no algorithm that will enumerate all possible true mathematical statements ... but that is saying something very different to what you asserted.)

(There is a subtle relationship between decidability and computability, but once again that is not what Godel's theorems are saying ... directly. Plainly, Godel's theorems are not directly about algorithms.)

How do we know if a problem can be solved using algorithm?

I don't know if there is an answer to that, either in the sense of all problems being solvable, or any specific problem being solvable.

(But it is also unclear what you mean by "problem" and "solve". For example, if you equate "problem" with a mathematical theorem, and "solving" with finding a proof / disproof, then clearly Godel's theorem says that there is a class of problems that cannot be solved by any means ... including algorithmically ... because no solution exists.)

How do we know that NP problems are algorithmically solvable?

Again ... there is uncertainty in what you mean by "solveable".

@delnam comments thus:

"In an fixed NP problem, the time to check the solution is bounded above by some fixed polynomial T. Therefore the size of any solution to an instance of this NP problem is also bounded above by a fixed polynomial S. Therefore, for any given input of size n, the space of possible solutions is always finite (roughly 2^S(n) solutions) and can be searched exhaustively. Therefore all NP problems are decidable."

If you exclude the impractical "exhaustive search" algorithm, then I don't think there is a general way to know ... apart from hard work, either to find an existing (better) algorithm (for the problem or an equivalent one), or develop one de novo.

  • In an fixed NP problem, the time to check the solution is bounded above by some fixed polynomial T. Therefore the size of any solution to an instance of this NP problem is also bounded above by a fixed polynomial S. Therefore, for any given input of size n, the space of possible solutions is always finite (roughly 2^S(n) solutions) and can be searched exhaustively. All NP problems are decidable. – user7043 Oct 17 '15 at 7:35
  • "They are actually about whether all mathematical statements can be proved or disproved.": As far as I can remember, the existence of certain formal proofs is related to the existence of an algorithm that can find them. So there may be some relation between the incompleteness theorem and results in computability. I am not sure though. – Giorgio Oct 17 '15 at 8:19
  • @Giorgio There is a relationship but it is very subtle. Too subtle to do it justice in one comment, and I'm not going to write a whole answer that's off-topic and probably wastes on the OP who doesn't seem to have a good grasp of either computability or logic. – user7043 Oct 17 '15 at 8:28
  • @delnan: Fair enough, I only wanted to point out that this statement in Stephen's answer may be inaccurate. – Giorgio Oct 17 '15 at 9:02
  • 1
    @Giorgio - I disagree that what I said is inaccurate. The OP is saying / implying that Godel applies >>directly<< to computation theory. That is incorrect. Anyhow, I've updated by answer to clarify this. – Stephen C Oct 18 '15 at 2:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.