3 ms·
Any chance OP is referring to "integer programming" (aka discrete optimization), which came about 20 years later?
by martinlaz 8y ago
Any chance OP is referring to "integer programming" (aka discrete optimization), which came about 20 years later?
- atq2119 8y agoNo. Integer programming in the operations research sense is "just" solving linear optimization problems with the constraint that the solution variables need to be integer. In particular, IP doesn't really involve the multiplicative structure of the integers, which is crucial for how Gödel proved his results. Also, I'd point out that while there's significant overlap between integer programming and discrete optimization, they're not the same thing. Integer programming is one tool used in discrete optimization among many.
- fnrslvr 8y agoAdding to atq2119's answer, integer programming is merely NP-complete. You really need full Turing computability to get the incompleteness results. The set of provable consequences of Peano arithmetic is RE-complete, and we know that NP != RE, so you definitely can't give an integer program that verifies that a formula is provable from PA, which is a necessary ingredient.