8
Non-deterministic Polynomial Completeness
- NP-hard and NP-complete define the computational complexity of algorithms.
In this chapter, we introduce the theory of intractability, that is, discuss whether a problem can be solved in polynomial time or not, that is, P, Non-deterministic Polynomial (NP) Problems are discussed. The classification of problems into NP-hard problems and NP-complete (NPC) problems is explained with examples.
8.1 NP-hard and NP-complete
8.1.1 Classification of Problems
The subject of computational complexity theory is focused on classifying problems by how hard they are. There are many different classifications depending on the time taken by the problem. The following are the types of classification.
- P problems are ...
Get Formal Languages and Automata Theory now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
