P and NP

Analysis and Design of Algorithms

Jesus A. Gonzalez

July 17, 2019

NP-Completeness

Content

Part 1 Introduction - Computers, Complexity, and Intractability

Theory of NP-Completeness

Theory of NP-Completeness

Theory of NP-Completeness

Basic Concepts

Basic Concepts

Basic Concepts

Basic Concepts

Basic Concepts

Basic Concepts

Basic Concepts

Basic Concepts

Basic Concepts

Basic Concepts

Time Complexity Function

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Polynomial Time Algorithms and Intractable Problems

Probably Intractable Problems

Probably Intractable Problems

Probably Intractable Problems

Probably Intractable Problems

Probably Intractable Problems

NP-Complete Problems

NP-Complete Problems

NP-Complete Problems

NP-Complete Problems

NP-Complete Problems

NP-Complete Problems

Part 2: The Theory of NP-Completeness

Decision Problems, Languages, and Encoding Schemes

Decision Problems, Languages, and Encoding Schemes

Example of Well Known Decision Problems

Example of Well Known Decision Problems

Formal Language

Formal Language Setting

Formal Language Setting

Deterministic Turing Machines and the Class P

Deterministic Turing Machines and the Class P

Deterministic Turing Machines and the Class P - Example

-Image from (Garey and Johnson, 1979)

Deterministic Turing Machines and the Class P - Example

-Image from (Garey and Johnson, 1979)

Deterministic Turing Machines and the Class P - Example

Deterministic Turing Machines and the Class P

Deterministic Turing Machines and the Class P

Deterministic Turing Machines and the Class P

Deterministic Turing Machines and the Class P

\(\begin{aligned} T_M(n) = {} & \text{max} \lbrace m : \mbox{there is an } x \in \Sigma^* \mbox{, } \mbox{with } |x|=n \mbox{, such that}\\ & \mbox{the computation of } M \mbox{ on input } x \mbox{ takes time } m \rbrace \end{aligned}\)

Deterministic Turing Machines and the Class P

The P Class

\(\begin{aligned} P = {} & \lbrace L : \mbox{there is a polynomial time DTM program } M\\ & \mbox{ for which } L = L_M \rbrace \end{aligned}\)

Non Deterministic Computation and the Class NP

Non Deterministic Computation and the Class NP

Non Deterministic Computation and the Class NP

Non Deterministic Computation and the Class NP

Non Deterministic Computation and the Class NP

Non Deterministic Computation and the Class NP

Non Deterministic Computation and the Class NP

Non Deterministic Computation and the Class NP