3 ms·
You're misunderstanding something. P=NP is about whether two sets are equal. If it's "undecidable" or "independent", then ZFC is consistent with either P=NP or
by shotwell 11y ago
You're misunderstanding something. P=NP is about whether two sets are equal. If it's "undecidable" or "independent", then ZFC is consistent with either P=NP or P \neq NP.
- mtdewcmu 11y agoIndependent doesn't sound like the same thing as undecidable. Given a program P, it is undecidable whether that program will halt. There is an answer: P either halts or it doesn't. There is just no way to find out (in general).
- shotwell 11y agoYes, 'undecidable' is used for a similar class of mathematical problems. For example, the continuum hypothesis - another question about an equality of sets - is undecidable in ZFC. This notion is strongly related to undecidability on Turing machines (possibly equivalent, depending on how you look at it).
- johncolanduoni 11y agoThey are intimately related. If you look at how Gödel's incompleteness theorem is stated, the existence of "effective procedures" (I.e. Computable functions) figures in intimately. A good overview of this in a reasonably accessible format can be found here: http://www.scottaaronson.com/blog/?p=710 http://www.scottaaronson.com/blog/?p=710 The same author wrote a good treatment of the implications of the undecidability of P=NP: http://www.scottaaronson.com/papers/pnp.pdf http://www.scottaaronson.com/papers/pnp.pdf Scott Aaronson is probably one of the best at explaining theoretical computer science, if you're interested in these topics you should follow his blog.