37 ms·
I'd be surprised if the average person who's been out of school and programming for at least a decade, let alone moved mostly on to managing programmers, could
by khafra 16y ago
I'd be surprised if the average person who's been out of school and programming for at least a decade, let alone moved mostly on to managing programmers, could still remember the difference between an NP complete problem and the halting problem at an "can explain it to your grandmother" level.
- vog 16y agoI 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.