P, NP, NP-Complete, and NP-Hard Problems

The terms P, NP, NP-Complete, and NP-Hard are tossed around a lot in computer science research. These terms categorize different kinds of problems. The exact definitions are surprisingly difficult to deal with so I simplify their definitions in my head when I encounter the terms. An annoying glitch is that the definitions depend on the unsolved “P equals NP or not problem”; I always assume that P != NP. Problems are categorized based on how easy or difficult it is to verify a given solution, and by how easy or difficult it is to find a solution in the first place. In terms of overall difficulty, from low to high difficulty, problem categories are P, NP, NP-Complete, NP-Hard.

A problem is P if it is easy to verify a particular solution and easy to find a solution. Now the term “easy” is relative and means . . . well let’s just say easy means computable in a practical amount of time in many but not all situations. A problem is NP if a solution is definitely easy to verify but finding a solution may or may not be easy. A problem is NP-Complete if a given solution is definitely easy to verify and finding a solution is definitely very difficult. A problem is NP-Hard if it is definitely very difficult to solve but verifying a given solution may or may not be easy. Now these approximate definitions aren’t completely correct but they’re good enough to make sense of a research paper that tosses the terms around.

This entry was posted in Machine Learning, Software Test Automation. Bookmark the permalink.