Content deleted Content added
mNo edit summary |
Added a comment concerning Gödel's Incompleteness Theorem |
||
Line 222:
[[User:Easwaran|Easwaran]] ([[User talk:Easwaran|talk]]) 12:12, 14 September 2009 (UTC)
:This is not what Gödel's Incompleteness Theorem is about. It just says that for a "sufficiently strong" logic+theory, there are statements that must be labeled "true" but cannot be proved within that system (but possibly can be proved via another meta-system) (Also, Gödels canonical example of a self-referential statement has a bad smell as frankly it seems to me he intermixes truth values from different levels with scant justification, but that's another topic). If you stay in First-Order Logic + Some Theory (e.g. Arithmetic), it intuitively seems correct to say that if "problems that are easy to check are easy to solve" (i.e. P=NP) then "finding a proof" of a provable statement should be about as easy as "checking a proof" of a provable statement (which is known easy). This needs to be made more precise of course. [[User:There is a T101 in your kitchen|There is a T101 in your kitchen]] ([[User talk:There is a T101 in your kitchen|talk]]) 21:22, 8 October 2016 (UTC)
== Graph Theory ==
| |||