O'Reilly logo

Formal Languages and Automata Theory by K.V.N. Sunitha

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8

Non-deterministic Polynomial Completeness

  1. 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.

  1. P problems are ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required