Re:Classic Nintendo Games Are NP-Hard (2012)
by nitrogen on Thursday December 28, 2017 @12:14PM
(#16023291)
...your answer is so far off the mark I'd recommend passing in an interview based on that alone.
What kind of work do you do that requires regular detailed analysis of the complexity class of algorithms?
It's been my experience that it's enough for an engineer to be able to say, "This algorithm will (not) run in an acceptable time for our expected input sizes," and that the precise definitions of NP complete and NP hard are best forgotten and looked up on Wikipedia when needed.
> it's impossible to predict the best solution without brute forcing all possible combinations of action
That's not true; all possible combinations are not required to be checked; frequently a greedy algorithm can eliminate the majority of possibilities without actually checking them.
"Impossible" is also a very strong word.
Furthermore, there are plenty of problems where we currently can't solve them without bruteforce ("impossible" to do so), but we don't know if they're NP-complete/even in the NP-class.
However, the really important detail you're missing which makes your answer completely wrong is the verification of the proof.
If a problem is of NP Complexity, than it must be computationally easy to determine that an answer is correct in polynomial time.
Your answer simply stated that a solution could be found by brute-forcing, not that the answer is easy to verify once found, and not that said brute-forcing must not be in non-polynomial time.
By missing those two details, your answer is so far off the mark I'd recommend passing in an interview based on that alone.