Godel showed that in any consistent proof system, there are true statements that the system cannot prove. Take for example the statement: "This proof system cannot prove this statement."
This has nothing to do with undecidability, which deals with functions (or sets), not statements. An undecidable function one that no machine can be built to calculate (an undeciable set one which has no decidable function that determines membership of the set).
Actually, Godel's theorm has everything to do with undecidability. Godel's theorem is an "incompleteness" theorm. A system which is incomplete contains undecidable formulae.
I don't think you understand the text book definitions you are quoting and the connections between them.
Check out this interesting transcript of a talk by Chaitin.
Goedel showed that there are infinitely many unsolvable problems in the world
Godel proved that there exist true statements in any suitably expressive language (any language which is expressive enough to be useful) which cannot be proven using that language.
Turing proved this as well, but used a different approach, the Turning machine, and thus the set of problems know as "undecidable" was born.
but there's no guarantee that this infinity of problems consists of interesting problems. In fact, they might all be dull ones!
There are many useful and interesting problems that are unfortuantely undecidable. For example, proofs in any suitably expressive logical calculus are undecidable. One of the main goals of the field of mathematics is now known to be impossible: prove all true statements in mathematics starting from a fixed number of very simple axioms. There are an infinite number of axioms. And they can be abitrarily complex. This leaves us wondering things like if P!=NP are true, but cannot be proven starting from the statements that we feel comfortable calling axioms. And nobody is about to call P!=NP an axiom.
It looks like they trade off exponential time with exponential space...
Right. The only exception that I'm aware of to this rule is quantum computing since a quantum computer can simultaneously be in an exponential number of states relative to its size.
You still need to increase the size of the quantum computer if you wish to increase its speed for highly parallel problems, but its ability to handle parallel states would increase "faster" than its size.
Slashdot Mirror
Godel showed that in any consistent proof system, there are true statements that the system cannot prove. Take for example the statement: "This proof system cannot prove this statement."
This has nothing to do with undecidability, which deals with functions (or sets), not statements. An undecidable function one that no machine can be built to calculate (an undeciable set one which has no decidable function that determines membership of the set).
Actually, Godel's theorm has everything to do with undecidability. Godel's theorem is an "incompleteness" theorm. A system which is incomplete contains undecidable formulae.
I don't think you understand the text book definitions you are quoting and the connections between them.
Check out this interesting transcript of a talk by Chaitin.
Ah, you're right. It sounds like he's describing a Euclidean Steiner tree problem in the solution.
Goedel showed that there are infinitely many unsolvable problems in the world
Godel proved that there exist true statements in any suitably expressive language (any language which is expressive enough to be useful) which cannot be proven using that language.
Turing proved this as well, but used a different approach, the Turning machine, and thus the set of problems know as "undecidable" was born.
but there's no guarantee that this infinity of problems consists of interesting problems. In fact, they might all be dull ones!
There are many useful and interesting problems that are unfortuantely undecidable. For example, proofs in any suitably expressive logical calculus are undecidable. One of the main goals of the field of mathematics is now known to be impossible: prove all true statements in mathematics starting from a fixed number of very simple axioms. There are an infinite number of axioms. And they can be abitrarily complex. This leaves us wondering things like if P!=NP are true, but cannot be proven starting from the statements that we feel comfortable calling axioms. And nobody is about to call P!=NP an axiom.
It looks like they trade off exponential time with exponential space...
Right. The only exception that I'm aware of to this rule is quantum computing since a quantum computer can simultaneously be in an exponential number of states relative to its size.
You still need to increase the size of the quantum computer if you wish to increase its speed for highly parallel problems, but its ability to handle parallel states would increase "faster" than its size.
Want to find the shortest set of roads to build to interconnect a bunch of cities?
This is the minimum spaning tree problem. This is not an NP hard problem.
Let V = number of vertices
Let E = number of edges
This problem can be solved in O(E + Vlg(V)).