According to Godel'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?
2026-03-27 10:11:23.1774606283
Godel's Incompleteness Theorem and Algorithms
87 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
We know a problem can be solved by an algorithm (it's computable) by exhibiting an algorithm that solves it. Or by showing that the problem can be reduced – transformed by an algorithm – into another problem for which we know an algorithm. You can take "algorithm" to mean program in your favorite programming language.
NP problems are by definition computable: some machine computes the problem. In the case of problems in NP, the machine is nondeterministic ("NP" stands for "Nondeterministic Polynomial-time"), but the computation performed by this abstract machine can be performed by a deterministic machine, one which takes at worst exponentially longer to arrive at answers.