3 ms·
I disagree, because the NP completeness and halting problem are very different concepts. Confusing those means not having understood them in the first place. H
by vog 16y ago
I disagree, because the NP completeness and halting problem are very different concepts. Confusing those means not having understood them in the first place.
However, things would be different if it was about something like "NP hard" vs. "NP complete" vs. "NP". That kind of details are easily forgotten if one doesn't work in that field.
- khafra 16y agoWell, BQP and FBQP are very different concepts, but I doubt anyone who hasn't actively studied complexity theory in the last few years could explain the difference. Same goes for NP-complete and Entscheidungsproblem; if you don't use it, you lose it. I mean, anybody with a CS degree should know that the halting problem has something to do with predicting whether a given Turing machine will ever stop; but that's not "explain it to your grandmother" level.