What does NP stand for?
(Not that I have the requisite knowledge to understand it).
It is widely believed that some problems in NP are not also in P, i.e. that the solutions cannot be found in polynomial time. Note that brute force may not be the most efficient way to solve such problems. For example, integer factorization is believed to not be in P, but the best known solution is much better than brute force.
NP Hard problems are problems that can be used to solve all other NP problems with only polynomial time overhead. For instance, you can "encode" any NP problem as a 3COLOR problem, and then solve the 3COLOR problem instead. The reason NP hardness is interesting is that if you could solve an NP hard problem in polynomial time, then all of NP can be solved in polynomial time, so P=NP.
Not all NP hard problems are actually in NP. In other words, there are some problems that can be used to solve any NP problem, but whose solutions cannot be verified in deterministic polynomial time. The problems in NP that are also NP hard are called NP complete problems; 3COLOR is an example of such a problem. If you can prove that a given NP complete problem cannot be solved in deterministic polynomial time, it means P!=NP.
Strictly speaking, NP isn’t so much about the finding of solutions, just the verification of their correctness. The finding part is P [edit: which is contained in NP].
P=NP would mean that if we can easily verify a solution , then we can also find it easily in the first place. P!=NP means that there are some problems which are easy to verify the solution for,but hard to find a solution for.
Because nitpicking is fun, I'll add my contribution and say that the traditional definition of NP is actually about the finding of solutions, and is the etymology of the phrase "non deterministic polynomial time". That is, a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time.
Of course, since our non deterministic algorithm could just be the enumerate all witnesses, and verify them, then the two definitions are equivalent, except for the verification-based one being much more intuitive.
Which is exactly what quantum computers can do for certain classes of problems, such as integer factorization.
Sadly, it seems not to be the case (or not yet found?) for the most well known and useful class of NP problems, NP-complete.
See this discussion https://news.ycombinator.com/item?id=1371150
> 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.
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.
An example would be 3-SAT, which takes a boolean predicate of a particular form (that it is conjunctions of disjunctions of 3 variables), and then an assignment of the variables, and checks if it satisfies the predicate. You can do this in polynomial time, so 3-SAT is in NP.