Cook’s Theorem

Table of Contents

Cook’s Theorem

Theoretical Foundations

Decision Problems & Algorithms

The Elements of NP

What The Theorem Must Do

The Structure of MX I

The Structure of MX II

The Structure of MX III

The Structure of MX IV

The Structure of MX V

The Structure of MX VI

Starting Position

The Transform

The Variables

The Meaning of the Variables

Clause Groups

Clause Groups II

Group G1

G1 Clause Meanings

Group G2

G2 Clause Meanings

Group G3

Group G3 Continued

G3 Clause Meanings

Group G4

G4 Clause Meanings

Group G5

Group G6

Group G6 Continued

Deriving CNF Form

Final Group

G6 The Final Step

Windup

Email: Peter_Maurer@Baylor.edu

Home Page: http://cs.baylor.edu/~maurer

Best experienced with

Click here to start.

Download presentation source