程序代写代做代考 algorithm Java How To Think Like A Computer Scientist

How To Think Like A Computer Scientist

Reductions &
NP-Completeness
Jeff Edmonds
York University

Quick Defn and Reduction
History
Course vs Schedule
More about Reductions
Circuit vs Airplane
Circuit vs 3-Colouring
Conclusion
Definitions for 2001/3101
More Classes for 4111
More Detailed Steps for 6111
Thinking about Algorithms Abstractly
Intro & EECS 2001/3101/4111/6111
Not covered

Computable

Exp

Poly

Known
GCD
Matching
Halting

NP
SAT
Games

complete
poly Prob’
NP-Complete

NP-Complete

A Quick Reduction
{G,k | Are there k vertices that
cover all the edges}

Goal: Prove PVC “likely” has no poly time alg.
There are many steps to the proof.
If you try to think about them all at once
you will panic and drown.
Understand each by itself.
Each is simple.

PVC =
vertex cover

Worry about
nothing else.

A Quick Reduction
Step 0: Overview

A  P3-SAT is not likely in Poly.
B  PVC is not likely in Poly.
Proved already
Want to prove.
Prove: A  B
Same as: B  A
PVC is in Poly
Design an algorithm for P3-SAT
(Using an oracle for PVC as a subroutine)
 P3-SAT is in Poly
A
B 
But A is true. So B is true.

Worry about
nothing else.
3-SAT ≤
Goal Accomplished: Proved PVC not likely in Poly.
{G,k | Are there k vertices that
cover all the edges}

A Quick Reduction
Step 1: Know what
an oracle for PVC is.
Vertex Cover

GIVEN:
Oracle for PVC
G,k
Can you select k vertices
so that each edge
is covered by one of them?

Worry about
nothing else.
Yes
No

k=7
vertices = cities
edges = roads
Build k gas stations in cities
Can you service
all the roads?

A Quick Reduction
Step 1: Know what
an oracle for PVC is.
Vertex Cover

GIVEN:
Oracle for PVC
G,k
Can you select k vertices
so that each edge
is covered by one of them?

Worry about
nothing else.
Yes
No

k=7
We often call the algorithm assumed to exist, an Oracle.

Oops Yes
No

A Quick Reduction
Step 2: Know what
an alg for P3-SAT is.

(a or ⌐b or c) and (⌐a or ⌐b or ⌐c) 

BUILD:
Alg for P3-SAT

Yes there is a setting of the variables that satisfies it.
No it does not

Worry about
nothing else.
In 3-Sat
and of clauses
each with or of 3 variables

A Quick Reduction
Step 3: Design instant map from clauses to graph
and understand the effect.

Worry about
nothing else.
≈

For each variable a
T or F vertex must be taken to cover edge
k too small to take both.
a is true or false
not both

k = #var

A Quick Reduction
Step 3: Design instant map from clauses to graph
and understand the effect.

Worry about
nothing else.
≈

For each clause
(a or ⌐b or c)
This variable satisfies the clause.
Two vertices must be taken to cover edges
k too small to take three.

Clause to Variable Edges
One must be covered by
an assignment
to a variable.

k = #var
+ 2#clauses

A Quick Reduction
Step 3: Design instant map from clauses to graph
and understand the effect.

Clauses
Satisfiable

(a or ⌐b or c) and
(⌐a or ⌐b or ⌐c) 
≈
Graph
Satisfiable

a
T
F
a
b
T
F
c
T
F
⌐b
c
⌐a
⌐b
⌐c
k = #var
+ 2#clauses
a=T, b=T, c=F

Consider an assignment
that satisfies all clauses
Consider k vertices
that cover all edges.

A Quick Reduction
Step 3: Design instant map from clauses to graph
and understand the effect.

(a or ⌐b or c) and
(⌐a or ⌐b or ⌐c) 
≈

Because of k,
1 per variable
& 2 per clause

a
T
F
a
b
T
F
c
T
F
⌐b
c
⌐a
⌐b
⌐c
k = #var
+ 2#clauses
Consider an assignment
that satisfies all clauses
Clauses
Satisfiable

Graph
Satisfiable

Consider k vertices
that cover all edges.

a=T, b=T, c=F

A Quick Reduction

GIVEN:
Oracle for PVC

BUILD:
Alg for P3-SAT

Yes/No

Worry about
nothing else.
Step 4: Design algorithm for P3-SAT.
(a or ⌐b or c) and (⌐a or ⌐b or ⌐c) 

A Quick Reduction

GIVEN:
Oracle for PVC

BUILD:
Alg for P3-SAT

Yes/No

Worry about
nothing else.
(a or ⌐b or c) and (⌐a or ⌐b or ⌐c) 

Step 5: Prove algorithm for P3-SAT works.
Oracle for PVC says yes
Alg for P3-SAT says yes

This is what Alg for P3-SAT is supposed to do.
Clauses
Satisfiable
All edges can be covered by k vertices.

A Quick Reduction

Worry about
nothing else.
3-SAT ≤
Goal Accomplished: Proved PVC not likely in Poly.
{G,k | Are there k vertices that
cover all the edges}
Step 6: Conclusion

That was not so bad,

Colour each node.
Nodes with lines between them must have different colours.
Can you do it with 2 colours?
Can you do it with 3?

Graph Colouring

Please feel free to ask questions!

History of Classifying Problems

Known
Unknown

Euclid (300 BC)
GCD

Turing 1936
Gödel’s Incompleteness Theorem

Gödel 1931
Computational Problem:
MathTruth(Φ) = Math Statement Φ is true.
Proof System:
If S is a valid proof system,
then a proof P of Φ is a witness that Φ is true
& a proof P of Φ is a witness that Φ is false.
Running Time to find P :
Time = # of P that come before output proof.
= 2# bits to describe P
Godel’s 1956 lost letter:
Can this be done in time k(# of symbols to describe P )
This would eliminate the need for mathematicians.
He talks about problems of the form (∃ y) φ(y,x).
For NP, the P has the same size as the input,
so this asking whether NP = Linear Time

History of Classifying Problems

Known

GCD

Computable
Halting

Turing 1936

History of Classifying Problems

Computable

Known
GCD
Halting

Exp

Poly

Jack Edmonds 1965

History of Classifying Problems

Computable

Exp

Poly

Known
GCD
Matching
Halting

Jack Edmonds

Steve Cook

NP
exponential time to search
poly time to verify given witness
Non-Deterministic
Polynomial Time
Circuit-Sat Problem:
Does a circuit have a satisfying assignment.
SAT

History of Classifying Problems

Computable

Exp

Poly

Known
GCD
Matching
Halting

Jack Edmonds

Steve Cook
Circuit-Sat Problem:
Does a circuit have a satisfying assignment.

NP
Is it easier than
other exponential problems?
Games

SAT

History of Classifying Problems

Computable

Exp

Poly

Known
GCD
Matching
Halting

Jack Edmonds

Steve Cook
Circuit-Sat Problem:
Does a circuit have a satisfying assignment.

NP
Is it harder than
poly-time problems?
Games

SAT

History of Classifying Problems

Computable

Exp

Poly

Known
GCD
Matching
Halting

Steve Cook 1971
Circuit-Sat Problem:
Does a circuit have a satisfying assignment.

NP
Let’s compare
the problems in NP
SAT
Games
None are harder than SAT!

complete
poly Prob’
SAT

CoNP
not SAT

Computable

Exp

Poly

NP
GCD
SAT
Halting

Recognizable

CoRecognizable
Not Halting
Classes of Problems

Poly
GCD
Poly:
Problems P computable in polynomial.
 A,c  I A(I) = P(I) and Time(A,I)  |I|c
Polynomial Time

Each instance I
has an exponential number of possible solutions.
Each solution S is either valid or not
(sufficiently high value or not)
The output is
Yes, it has a valid solution.
No, it does not
the solution need not be returned
There is a poly-time alg Valid(I,S) to test
given an instance I and a solution S,
whether or not S is a valid solution of I.
Eg: Network Flows
Given I = ,
does network G have flow of value  k?

NP
Non-Deterministic Polynomial Time

Poly
Network Flows

NP
Non-Deterministic Polynomial Time
Example: Satisfiablity:
Instance: A circuit I.
Solution: A satisfying assignment S.
I is a yes instance iff there is such an assignment .
Given an instance I and a solution S,
there is a poly-time alg Valid(I,S) to test
whether or not S is a valid solution of I.
0 1 1 0 1 0 1
Assignment S:

1
Sat(I)=Yes iff  S Valid(I,S)
Circuit I:

SAT

Poly

NP
Formal definition:
Prob  NP iff  poly time Valid
such that Prob(I) = Yes iff  S Valid(I,S)
Non-Deterministic Polynomial Time
SAT

Poly
Sat(I)=Yes iff  S Valid(I,S)

Non-Deterministic Polynomial Time
Sat(I)=Yes iff  S Valid(I,S)
A Non-Deterministic TM/Java/… is
the same as a deterministic one,
except that its moves are not deterministic.
It has a “choice” as to which step to take next.
Deterministic:  (qi,c) =
Non-Deterministic:  ϵ 
A non-deterministic machine M on input I
is said to accept its input
if there exists an accepting computation.
Note problems computed need yes/no answers.

Poly
NP:

NP
If I is a “yes” instance:
A fairy god mother could provide you a small witness/solution/proof S with which you can prove to your non-believing poly time boss that I is a “yes” instance.
If I is a “no” instance:
There is likely no such witness/solution/proof .

Non-Deterministic Polynomial Time
SAT

Poly
CoNP:

NP
If I is a “No” instance:
A fairy god mother could provide you a small witness/solution/proof S with which you can prove to your non-believing poly time boss that I is a “no” instance.
If I is a “Yes” instance:
There is likely no such witness/solution/proof .

Non-Deterministic Polynomial Time

CoNP
not SAT
SAT

Poly

NP
Sat = { circuit C |  assignment S, C(S) = true }

Non-Deterministic Polynomial Time

CoNP
not SAT
SAT

If I is a “yes” instance:
A fairy god mother can provide you a proof S with which you can prove I is a “yes” instance.

Poly

NP
Sat = { circuit C |  assignment S, C(S) = true }
not Sat = { circuit C | assignment S, C(S) = false }

Non-Deterministic Polynomial Time

CoNP
not SAT

If I is a “no” instance:
A fairy god mother can provide you a proof S with which you can prove I is a “no” instance.
SAT

Poly

NP
Sat = { circuit C |  assignment S, C(S) = true }
not Sat = { circuit C | assignment S, C(S) = false }
P = { circuit C |  assignment S, C(S) = false }

Non-Deterministic Polynomial Time

CoNP
not SAT
P

S is a witness/solution/proof.
but of I is being a “yes” or a “no”?
a “yes” instance.
SAT

Poly

NP
SAT

CoNP
Network Flows
Network Flows:
Is there a flow in G with value  k?
A witness/solution/proof S of Yes is
a flow
A witness/solution/proof S of No is
a Cut.
In general, in NP and in CoNP
does not (likely) mean in P.
not SAT

Network Flows
Network Flows
Non-Deterministic Polynomial Time

Poly
GCD

NP vs Other Classes
If P Polynomial Time,
You don’t even need
the fairy good mother.
 P NP
If P NP,
then |S|  n1000
In time you can
try all witnesses S.
 P Exp

Exp
n1000
2
SAT
Games

Exp

Poly

Computable
GCD
SAT
Halting

Turing 1936
Games
NP vs Other Classes

Exp

Poly

Computable

Recognizable
GCD
SAT
If I= is a “yes” instance
M halts on I
the computation is a witness
arbitrarily long but finite.
If I is a “no” instance
M runs forever
there is no witness
Halting

CoRecognizable
Not Halting

CoNP
not SAT
Games
NP vs Other Classes

Computable

Exp

Poly

Known
GCD

NP
NP-Complete Problems
Problem Pnew  NP
Pnew not too hard.
Pnew
Test in poly-time
if a given solution
is valid

Computable

Exp

Poly

Known
GCD

NP
NP-Complete Problems
Pnew
Sat
Problem Pnew is NP-Hard
If being able to solve
this problem fast
means that you can
solve every problem
in the class fast.
PNP, P ≤poly Pnew
Easier: Sat ≤poly Pnew
Cook: P ≤poly Sat

Steve Cook

Computable

Exp

Poly

Known
GCD

NP
NP-Complete Problems
Problem Pnew is NP-Complete
Pnew  NP
Pnew is NP-Hard

Pnew

Computable

Exp

Poly

Known
GCD

complete
NP-Complete Problems
Problem Pnew is NP-Complete
Pnew  NP
Pnew is NP-Hard

Pnew
Sat

Steve Cook

Free Lunch

Industry would love a free lunch
Given a description of a good plane, automatically find one.
Given a circuit, find a satisfying assignment
Given a graph find a bichromatic coloring.
Given course description, find a schedule

X
X
X
X
X

Ingredients:
Instances: The possible inputs to the problem
(and desired cost).
Solutions for Instance: Each instance has an exponentially large set of solutions.
Valid: Each solution has an easy to compute cost or value.
Goal: The output is one of the valid solutions for this instance with optimal cost.
(minimum or maximum)
Optimization Problems

A large space of possibilities
Only a tiny fraction of which satisfy the constraints.
Brute force takes too long,
No feasible algorithm is known.
Rudich www.discretemath.com
If one has a fast algorithm
Then they all do.
If one has no fast algorithm
Then none do.
All of these problems
have a common story:

Course Scheduling

Given courses students want
and the time slots available
schedule courses to time slots
to minimize number of conflicts,
i.e. student wants two courses that are scheduled
at the same time.

Perspiration Search
Try all possible
Schedules
Too many to try.
A set of 50 courses has more
schedules than the number of atoms.

A Fast Algorithm
Is there a fast algorithm?
Most people think not.
We have not been able to prove that there is not.
It is one of the biggest open problems in the field.

A Graph

Represents
Cities & Roads
Computers & Networks
People & Friendships

A Colouring of a Graph
Colour each node.
Nodes with lines between them must have different colours.

Perspiration Search

Try all possible colourings
Too many to try.
A 50 node graph has more
colourings than the number of atoms.

A Fast Algorithm

Is there a fast algorithm?
Most people think not.
We have not been able to prove that there is not.
It is one of the biggest open problems in the field.

Problems are the Same!
Schedule each course.
Courses that conflict can’t be at same time.
Colour each node.
Nodes with lines between them must have different colours.

»
Two problems that are cosmetically different,
but substantially the same

Problems are the Same!
Schedule each course.
Courses that conflict can’t be at same time.
Colour each node.
Nodes with lines between them must have different colours.
»

English
Math
Science
course » node
can’t be scheduled
at same time
line between them

»
scheduled time » colour

1pm Mon
1pm Mon
3pm Fri

Act on
Act with
Constraint
Action

Algorithms Inter-Changeable

Colour Oracle

Sched.
Oracle

Given an oracle for
3-colorability, how can you quickly solve scheduling?

Algorithms Inter-Changeable
≤

Colour Oracle

Sched.
Oracle
Assume have an alg.
Proof by Reductions
Design an alg.

Algorithms Inter-Changeable
Courses & Conflicts

Colour Oracle

Sched.
Oracle

Schedule
Proof by Reductions

Colouring
≤

Algorithms Inter-Changeable
≥

Colour Oracle

Sched.
Oracle
Assume have an alg.
Proof by Reductions
Design an alg.

Algorithms Inter-Changeable

Colour Oracle

Sched.
Oracle

Colouring
Proof by Reductions
Schedule

Courses
& Conflicts

Algorithms Inter-Changeable
»

Colour Oracle

Sched.
Oracle
Proof by Reductions
But there is likely not a fast algorithm for either!!!

Please feel free to ask questions!

Reductions
Iharder

Iharder yes
Pharder
Iharder no
Ieasier

Ieasier yes
Peasier
Ieasier no

Two problems/languages Peasier and Pharder
each with their own definitions of
what a legal input is (Ieasier vs Iharder) and
which are yes-inputs and which no-inputs.

Reductions
Iharder

Iharder yes
Pharder
Iharder no
Ieasier

Ieasier yes
Peasier
Ieasier no

We want machines that decide/accept them.

Algharder
Pharder(Iharder)
Iharder
Peasier(Ieasier)
Ieasier

Algeasier

Reductions
Peasier ≤comp Pharder
Iharder

Iharder yes
Pharder
Iharder no
Ieasier

Ieasier yes
Peasier
Ieasier no

How do their complexities/difficulties compare?

Computable/Decidable

Exp

Poly

Co-NP

Recognizable

Co-Recognizable

Reductions
Peasier ≤comp Pharder
Iharder

Iharder yes
Pharder
Iharder no
Ieasier

Ieasier yes
Peasier
Ieasier no

It is hard to prove problem is Pharder hard.
It is easier to prove Peasier is easy.
by design an algorithm Algeasier for it.
But you only need to prove Peasier is at least as easy as Pharder .
Pretend you have an algorithm Algharder for Pharder
to use as a subroutine.

Reductions
Palg ≤comp Poracle
Ioracle

Ioracle yes
Poracle
Ioracle no
Ialg

Ialg yes
Palg
Ialg no

We often call the algorithm assumed to exist, an Oracle.

Given
Algoracle
Poracle(Ioracle)
Ioracle

Reductions
Palg ≤comp Poracle
Ioracle

Ioracle yes
Poracle
Ioracle no
Ialg

Ialg yes
Palg
Ialg no

We use Algoracle as an subroutine
in an algorithm Algalg for solving Palg.

Given
Algoracle
Poracle(Ioracle)
Ioracle

Build
AlgAlg
Palg(Ialg)
Ialg

Reductions
Palg ≤comp Poracle
Ioracle

Ialg

Algalg is given an input Ialg.

Given
Algoracle
Poracle(Ioracle)
Ioracle
Ioracle = InstanceMap(Ialg)

Build
AlgAlg
Palg(Ialg)
Ialg
InstanceMap

Ioracle
It maps it to input Ioracle.
and gives this to Algoracle.

Reductions
Palg ≤comp Poracle
Ioracle

Ialg

Algoracle gives the yes/no answer for his input Ioracle.

Given
Algoracle
Poracle(Ioracle)
Ioracle
Ioracle = InstanceMap(Ialg)

Build
AlgAlg
Palg(Ialg)
Ialg
Return same answer yesyes no no
InstanceMap

Ioracle yes
Poracle
Ioracle no
Algalg returns the same answer.

Reductions
Palg ≤comp Poracle
Ioracle

Ialg

To ensure Algalg works,
Ioracle = InstanceMap(Ialg) must

Given
Algoracle
Poracle(Ioracle)
Ioracle
Ioracle = InstanceMap(Ialg)

Build
AlgAlg
Palg(Ialg)
Ialg
Return same answer yesyes no no
InstanceMap

Ioracle yes
Poracle
Ioracle no

Ialg yes
Palg
Ialg no
map yes instances to yes instances and no to no.

Reductions
Palg ≤comp Poracle
Ioracle

Ialg

Must prove Algalg works.

Given
Algoracle
Poracle(Ioracle)
Ioracle
Ioracle = InstanceMap(Ialg)

Build
AlgAlg
Palg(Ialg)
Ialg
Return same answer yesyes no no
InstanceMap

Ioracle yes
Poracle
Ioracle no

Ialg yes
Palg
Ialg no
Ialg is a yes input  Ioracle is a yes input
 Algoracle says yes  Algalg says yes

Reductions

Palg ≤comp Poracle

Reductions
Reduction: Design an algorithm for one computational problem, using a supposed algorithm for another problem as a subroutine.
Used to create a new algorithm from a known algorithm.
Learn that a new problem is likely hard,
from knowing a known problem is likely hard.
Learn that two problems have a similar “structure.”

Palg ≤comp Poracle

GIVEN:
Network
Flow Oracle

BUILD:
Matching
Oracle
Matching ≤comp Network Flows
Who loves who

Ann
Fred
Sue
John
Beth
Bob
Mary
Sam

Max matching

A network

Max Flow

s
t

Reductions

Learn that a new problem
is likely hard, from knowing
a known problem is likely hard.
Reductions
Halting

Computable

Exp

Poly
Sat

If there is an
algorithm for Palg
then there is an
algorithm for Palg

then there is not fast
algorithm for Poracle
If there is not an
algorithm for Palg

If there is an
algorithm for Poracle

If there is not an
algorithm for Poracle

?
?

We give an algorithm for Palg using a
supposed algorithm for Poracle as a subroutine.
?
?
??
??
Reductions

Notation: Palg ≤poly Poracle
Palg is “at least as easy as” Poracle
(Modulo polynomial terms.)
Poracle is “at least as hard as” Palg
(Modulo polynomial terms.)
Conclusions:
We give an algorithm for Palg using a
supposed algorithm for Poracle as a subroutine.
Reductions
poly

x3
x2
x1
OR
OR
AND
AND
OR
NOT
F
F
F
F
F
T
The Circuit Satisfiablity Problem

This is a circuit with
AND/OR/NOT gates
with n input variables/wires
and one output wire.
This is an assignment giving
true/false, yes/no, 0/1
to each input variable.
These values percolate
down to the output wire.
x3
x2
x1
OR
OR
AND
AND
OR
NOT
The Circuit Satisfiablity Problem
The assignment satisfies
the circuit if the output is T.
F
F
F

F
F
T
F
T
F

x3
x2
x1
OR
OR
AND
AND
OR
NOT
The Circuit Satisfiablity Problem
F
F
F

F
F
T
F
T
F

Given a circuit,
what is a fast algorithm
to find a satisfying
assignment?
Or even to know whether
such an assignment
Try all possible
assignments
Too many to try.
50 input wires has more
assignments than
the number of atoms
We know no faster algorithm!

Instances: A circuit Icircuit.
Solution: An assignment Scircuit
Valid: Scircuit is a valid solution for instance Icircuit
if it satisfies it, i.e. Icircuit(Scircuit) = T
There is a poly-time alg Validcircuit(Icircuit,Scircuit) to test
whether or not Scircuit is a valid solution for Icircuit.
Goal: Given Icircuit, find a valid solution Scircuit.
Or determine if such a solution exists.
The Circuit Satisfiablity Problem

Pcircuit = { Icircuit | Circuit is satsisfiable
i.e. Scircuit, validcircuit(Icircuit,Scircuit) }

Instances: Requirements Iplane of the plane
i.e. cost, efficiency, safety, speed, weight. …
Solution: A description Splane of how to make the wing.
Valid: Given an instance Iplane and a solution Splane,
there is a poly-time alg Validplane(Iplane,Splane) to test
whether or not Splane is a valid solution for Iplane.
Goal: Given Iplane, find a valid solution Splane.
Or determine if such a solution exists.

Design an Airplane
Can be computed by a circuit C.
Pplane = { Iplane | Plane is buildable
i.e. Splane, validplane(Iplane,Splane) }

Reductions for Undecidability
Given an algorithm for Pcircuit,
I construct a working algorithm
for Pplane.
Proof Pcircuit is likely not in poly-time.
By way of contradiction assume it.
Contradiction because Pplane likely
does not have a poly alg.
Contrapositive:
I likely do not have a poly alg for Pplane,
hence I likely do not have one for Pcircuit.

{ Icircuit | Circuit is satsisfiable
Scircuit, validcircuit(Icircuit,Scircuit) }
{ Iplane | Plane is buildable
Splane, validplane(Iplane,Splane) }
≤

Reductions for Undecidability

Consider the form of the instances
of each problem
and which are yes-instances.

Icircuit

Isatisfiable
Pcircuit
Iunsatisfiable
Iplane

Ibuildable
Pplane
Iunbuildable
{ Icircuit | Circuit is satsisfiable
Scircuit, validcircuit(Icircuit,Scircuit) }
{ Iplane | Plane is buildable
Splane, validplane(Iplane,Splane) }
≤

Reductions for Undecidability

To ensure Algalg works,
Ioracle = InstanceMap(Ialg) must
InstanceMap
map yes instances to yes instances and no to no.
Icircuit

Isatisfiable
Pcircuit
Iunsatisfiable
Iplane

Ibuildable
Pplane
Iunbuildable
{ Icircuit | Circuit is satsisfiable
Scircuit, validcircuit(Icircuit,Scircuit) }
{ Iplane | Plane is buildable
Splane, validplane(Iplane,Splane) }
≤

Algorithms Inter-Changeable
≤

Circuit Sat
Oracle

Plane
Design
Oracle
Have an alg
for subroutine
Proof by Reductions
Design an alg.

Algorithms Inter-Changeable
Plane Requirements I

Circuit
Sat Oracle

Design
Plane
Oracle

Plane Description S
Proof by Reductions
C computes
Valid(I,?)

S
≤

Two problems that are cosmetically different, but substantially the same
Circuit ≤poly 3-Colouring

GIVEN: Alg for
3-colour
problem

BUILD:
Alg for circuit problem

Graph composed of gadgets that mimic the gates in C

colourable
or not

satisfiable
or not
Circuit ≤poly 3-Colouring

Circuit Problem:
instance = circuit
of gates
solution = true/false
to each variable
true/false
to internal wires
3-Colouring
instance = graph

solution = green/red/blue
to each node.
F
T
T

OR
OR

NOT
Output
x
y
z
G

Col

of gadgets

Circuit ≤poly 3-Colouring

A Graph Named
“Gadget”
Steven Rudich had computer search for graph with some key properties.

Colour each node.
Nodes with lines between them must have different colours.
Could you do it with 2 colours?

Colour each node.
Nodes with lines between them must have different colours.
Could you do it with 3 colours?

Yes.
How do we know?

Because we colored it!

X
Y
Output
variables&wires
~ nodes
gate ~ gadget
OR

x
y
Output

X
Y
Output

Consider your
colouring
T
F
true ~ green
false ~ red
? ~ yellow
F
T
OR

x
y
Output
T
red
yellow
green

X
Y
Output
true ~ green
false ~ red
? ~ yellow
OR

x
y
Output
F
T
T
red
yellow
green

Re-map your
colouring
T
F

T
F
X
Y
Output
?
gate function
~ gadget “function”
OR

x
y
Output

T
T

F
T

T
F

F
F
Or
Y
X

F
T
T
T
F
T
T

T
F
X
Y
Output
X Y Out
F F
F T
T F
T T

F
F
Consider your
colouring
gate function
~ gadget “function”
OR

x
y
Output
F
F
F

F
F

T
F
X
Y
Output
F
T

T
T
X Y Out
F F
F T
T F
T T

Consider your
colouring
gate function
~ gadget “function”
F
T
OR

x
y
Output
T

T
F
X
Y
Output
F
T
X Y Out
F F
F T
T F
T T

T
T
Consider your
colouring
gate function
~ gadget “function”
F
T
OR

x
y
Output
T

T
F
X
Y
Output
T
T

T
T
X Y Out
F F
F T
T F
T T

Consider your
colouring
gate function
~ gadget “function”
T
OR

x
y
Output
T
T

X
Y
Output

T
F
Consider your
colouring
X Y Or
F F F
F T T
T F T
T T T

Or – Gadget
gate function
~ gadget “function”
F
T
OR

x
y
Output
T

T
F
X
Y
Output
F
T

T
T
X Y Or
F F
F T
T F
T T

Proof
Or – Gadget
gate function
~ gadget “function”
F
T
OR

x
y
Output
T

T
F
X
Output
X NOT
F T
T F

NOT – Gadget

OR
OR

NOT
x
y
z

x
y
z
Output
Output

OR
OR

NOT
x
y
z

x
y
z
OR
Output
Output

OR
OR

NOT
x
y
z

x
y
z
Not
Output
Output

OR
OR

NOT
x
y
z

x
y
z
OR
Output
Output

OR
OR

NOT
x
y
z

x
y
z

F
T
T

T
F

T
F
Satisfiabilty of this circuit
=
3-colourability of this graph
Output
Output

GIVEN: Alg for
3-colour
problem

BUILD:
Alg for circuit problem

Graph composed of gadgets that mimic the gates in C

colourable
or not

satisfiable
or not
Circuit ≤poly 3-Colouring

Reduction

Two problems that are cosmetically different, but substantially the same

Satisfiability of this circuit
=
3-colourability of this graph

Please feel free to ask questions!

Free Lunch

X
X
X
X
X

NP-Complete Problems
A very large class of problems:
Industry would love to solve them quickly
We don’t know how.
If we could solve one quickly,
Þ we could solve all quickly.
If one impossible to solve quickly
Þ all impossible to solve quickly.

Boss assigns task:
Given courses students want,
schedule them to minimize conflicts.

Everyday industry asks these questions.

Your answer:
Sorry. Very likely no fast algorithm exits that always finds best schedule.

Worthy of wealth
& Nobel prize

Else have fast algorithm for all NP-problems.

Cryptography
Sometimes it is useful to know that a problem is computationally hard to do.
For example, breaking into your secret documents.

Please feel free to ask questions!

The End
(Of quick overview of NP)

Reductions &
NP-Completeness
Jeff Edmonds
York University

Classes of Problems
Non-Deterministic Polynomial Time
NP vs Other Classes
NP-Complete
Reductions

Thinking about Algorithms Abstractly
Thanks
Intro & COSC 3101/4111/6111
Definitions Needed
For 2001/3101

CoNP
not SAT

Computable

Exp

Poly

NP
GCD
SAT
Halting

Recognizable

CoRecognizable
Not Halting
Classes of Problems

125

Poly
GCD
Poly:
Problems P computable in polynomial.
 A,c  I A(I) = P(I) and Time(A,I)  |I|c
Polynomial Time

126

NP
Non-Deterministic Polynomial Time

Poly
Network Flows

1
Sat(I)=Yes iff  S Valid(I,S)
Circuit I:

SAT

Poly

NP
Formal definition:
Prob  NP iff  poly time Valid
such that Prob(I) = Yes iff  S Valid(I,S)
Non-Deterministic Polynomial Time
SAT

Poly
Sat(I)=Yes iff  S Valid(I,S)

129

130

Poly
NP:

Non-Deterministic Polynomial Time
SAT

131

Poly
CoNP:

Non-Deterministic Polynomial Time

CoNP
not SAT
SAT

132

Poly

NP
Sat = { circuit C |  assignment S, C(S) = true }

Non-Deterministic Polynomial Time

CoNP
not SAT
SAT

If I is a “yes” instance:
A fairy god mother can provide you a proof S with which you can prove I is a “yes” instance.

133

Poly

NP
Sat = { circuit C |  assignment S, C(S) = true }
not Sat = { circuit C | assignment S, C(S) = false }

Non-Deterministic Polynomial Time

CoNP
not SAT

If I is a “no” instance:
A fairy god mother can provide you a proof S with which you can prove I is a “no” instance.
SAT

134

Poly

NP
Sat = { circuit C |  assignment S, C(S) = true }
not Sat = { circuit C | assignment S, C(S) = false }
P = { circuit C |  assignment S, C(S) = false }

Non-Deterministic Polynomial Time

CoNP
not SAT
P

S is a witness/solution/proof.
but of I is being a “yes” or a “no”?
a “yes” instance.
SAT

135

Poly

NP
SAT

Network Flows
Network Flows
Non-Deterministic Polynomial Time

Poly
GCD

NP vs Other Classes
If P Polynomial Time,
You don’t even need
the fairy good mother.
 P NP
If P NP,
then |S|  n1000
In time you can
try all witnesses S.
 P Exp

Exp
n1000
2
SAT
Games

137

Exp

Poly

Computable
GCD
SAT
Halting

Turing 1936
Games
NP vs Other Classes

Exp

Poly

Computable

Recognizable
GCD
SAT
If I= is a “yes” instance
M halts on I
the computation is a witness
arbitrarily long but finite.
If I is a “no” instance
M runs forever
there is no witness
Halting

CoRecognizable
Not Halting

CoNP
not SAT
Games
NP vs Other Classes

Computable

Exp

Poly

Known
GCD

NP
NP-Complete Problems
Problem Pnew  NP
Pnew not too hard.
Pnew
Test in poly-time
if a given solution
is valid

Computable

Exp

Poly

Known
GCD

Steve Cook

141

Computable

Exp

Poly

Known
GCD

NP
NP-Complete Problems
Problem Pnew is NP-Complete
Pnew  NP
Pnew is NP-Hard

Pnew

Computable

Exp

Poly

Known
GCD

complete
NP-Complete Problems
Problem Pnew is NP-Complete
Pnew  NP
Pnew is NP-Hard

Pnew
Sat

Steve Cook

Computable

Exp
Poly

Known

complete
GCD
Matching
SAT

CoNP

complete
not SAT
Halting
Games
Most “natural” problems in NP
are either
in PolyTime
or NP-Complete
except?

NP-Complete Problems

Computable

Exp
Poly

Known

complete
GCD
Matching
SAT

CoNP

complete
not SAT
Factoring
Graph
Isomorphism
Halting
Games
Most “natural” problems in NP
are either
in PolyTime
or NP-Complete
except
NP-Complete Problems

Reductions
Reduction: Design a fast algorithm for one computational problem, using a supposedly fast algorithm for another problem as a subroutine.
Palg ≤poly Poracle

The End
(Of definitions for 2001/3101)

/docProps/thumbnail.jpeg

Related Posts