Close but no cigar. It means that you can verify a solution in polynomial time. Remember that P is contained in NP i.e. some NP problems can also be solved in

Close but no cigar. It means that you can verify a solution in polynomial time. Remember that P is contained in NP i.e. some NP problems can also be solved in deterministic polynomial time. 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.