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

How To Think Like A Computer Scientist

Reductions &
NP-Completeness
Jeff Edmonds
York University

See 2001 slides

More Classes for 4111
More Detailed Steps for 6111
Thinking about Algorithms Abstractly
Thanks
Intro & COSC 3101/4111/6111

Thinking about Algorithms Abstractly
More Classes
For 4111
COSC 3101/4111/6111
Reductions &
NP-Completeness
Jeff Edmonds
York University

A Problem P is said to be
computable/decidable/recursive
if on every input the machine
halts and give the correct answer.

Acceptable

Computable
Non-Deterministic Machines

Acceptable

Computable
Three equivalent definitions for a problem P
Acceptable:  TM M
On every yes input, the machine halts
and gives the correct answer.
On every no input, the machine
could halt and gives the correct answer
or could run for ever.
Witnesses:
 computable Valid such that P(I) =  S Valid(I,S)
Enumerable:  TM M
Every yes input I, is eventually printed.
No no input is ever printed.

Non-Deterministic Machines

Acceptable

Computable
Is there a language
that can be accepted
but not computed?
Turing proves uncomputable.
Alg: Run M on I.
If it halts halt and say “yes”
If it does not halt run forever.
Halting(M,I)
= Does TM M halt
on input I.
Halting
Non-Deterministic Machines

The Post Correspondence Problem (PCP)
The input is a finite collection of dominos
A solution is a finite sequence of the dominos
b
ca

a
ab

ca
a

abc
c

a
ab

So that the combined string on the top
is the same as that on the bottom
a b c a a a b c
a b c a a a b c
b
ca

,
a
ab

,
ca
a

,
abc
c

I =
Non-Deterministic Machines

I can give a solution as a witness.

b
ca

a
ab

ca
a

abc
c

a
ab

Non-Deterministic Machines

I can give a solution as a witness.
But how big is
this witness?

Exp

Poly

Computable

Acceptable
If dominos can’t be repeated,
|S|  |I|
If dominos can be repeated,
|S| can be arbitrarily long.
PCP?
PCP?

Without
Repeats
With
Repeats

CoNP
not SAT

Computable

Exp

Poly

NP
GCD
SAT
Halting

Acceptable

CoAcceptable
Not Halting
Non-Deterministic
Yes instances I
have accepting
computations
have witness/solutions.
No instances I
Do not.
Co-Non-Deterministic
No instances I
have accepting
computations
have witness/solutions.
Yes instances I
Do not.
Non-Deterministic Machines

Thinking about Algorithms Abstractly
In More Depth
Non-Deterministic Poly-Time
Reductions
NP vs Co-NP Preserving Reductions
NP-Complete
K-Clique vs K-Independent Set
12 Steps
Any P ≤ Sat
3-Col ≤ 3-Sat
Sat ≤ 3-Col
More Problems
12 Steps in More Depth
COSC 3101/4111/6111
Reductions &
NP-Completeness
Jeff Edmonds
York University

An optimization problem
Each solution is either valid or not (no cost)
The output is
Yes, it has a valid solution.
No, it does not
the solution is not returned
Eg: Given graph and integer ,
does G have a clique of size k?
Non-Deterministic
Poly-Time Decision Problems (NP)

Key: Given
an instance I (= )
and a solution S (= subset of nodes)
there is a poly-time alg Valid(I,S) to test
whether or not S is a valid solution for I.
Poly-time in |I| not in |S|. |S| can’t be too big.

k=4
Valid

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

Key:
If the instance has a valid solution
A non-deterministic (fairy god mother)
could prove it to you by giving you
such a solution as a witness.
You could check that it is valid.
You could convince your boss.

k=4
Valid

Non-Deterministic Poly-Time (NP)

Key:
If the instance does not have a valid solution
A non-deterministic (fairy god mother)
could prove it to you by giving you
????
You have no way to convince your boss.

k=5

Non-Deterministic Poly-Time (NP)

Example: 3-Col:
Instance: A graph G.
Solution: Colouring C nodes of G with 3 colours
such that every edge has two colours.
G is a Yes instance if there is such a colouring.
Given an instance G and a solution C,
there is a poly-time alg Valid(G,C) to test
whether or not C is a valid 3-colouring of G.
 3-Col  NP.
G

Col

Non-Deterministic Poly-Time (NP)

Example: Not 3-Col:
Instance: A graph G.
Solution: Colouring C nodes of G with 3 colours
such that every edge has two colours.
G is a No instance if there is not such a colouring.
Given an instance G and a solution C,
there is a poly-time alg Valid(G,C) to test
whether or not C is a valid 3-colouring of G.
 Not 3-Col  NP.
 Not 3-Col  Co-NP.

I can’t witness
Yes instances
G

Col

Non-Deterministic Poly-Time (NP)

Computable

Exp

Poly

Known
GCD

NP
Definition is asymmetric.
There is a witness that
a graph has a 3-Col.
There is no known witness that
a graph has no 3-Col.
3-Col

CoNP
Not 3-Col

Jack Edmonds

Steve Cook
Non-Deterministic Poly-Time (NP)

Example: Sorting
Instance: A list of numbers X=[x1,…xn].
Solution: Sorted order X’.
Given an instance X and a solution X’,
there is a poly-time alg Valid(X,X’) to test
whether or not X’ is a sorting of X.
 Sorting  NP.
Sorting is not a decision (Yes/No) problem.
X=[5,3,7,2]
X’=[2,3,5,7]

Non-Deterministic Poly-Time (NP)

Example: Parity
Instance: A list of bits X=[x1,…xn].
X is a Yes Instance if the number of xi=1 is odd.
 Parity  Poly-Time  NP.
X=[0,1,0,1,1,0]
parity=1

Don’t be lazy.
You can solve this on your own.
What do I give as a witness?
Non-Deterministic Poly-Time (NP)

Computable

Exp

Poly

Known
Parity

NP
3-Col
Games

CoNP
Not 3-Col

Jack Edmonds

Steve Cook
Parity  Poly-Time  NP.
Non-Deterministic Poly-Time (NP)

Example: Airplane Wing:
Instance: Requirements I of the wing.
Solution: A description S of how to make the wing.
I is a Yes instance if there is such a wing.
Given an instance I and a proof S,
there is a poly-time alg Valid(I,S) to test
whether or not S is a valid solution for I.
Airplane Wing  NP.

I = [weight, lift, cost, …]

Non-Deterministic Poly-Time (NP)

Example: Math Truth:
Instance: A math statement I
Solution: A proof S.
I is a Yes instance if there is such a proof.
Given an instance I and a proof S,
there is a poly-time alg Valid(I,S) to test
whether or not S is a valid solution for I.
Math Truth  NP.
Witness is way too big!

I = [ a,b,c,r  3 ar+br cr]

in |I|
not in |S|
Non-Deterministic Poly-Time (NP)

Example: Math Truth:
Instance: A math statement I
Solution: A proof S.
I is a Yes instance if there is such a proof.
Math Statement I can encode whether a TM stops
Halting problem poly Math Truth
 Math Truth  Undecidable.
I = [ a,b,c,r  3 ar+br cr]

Non-Deterministic Poly-Time (NP)

Computable

Exp

Poly

Known
GCD
Halting

NP
3-Col
Games

CoNP
Not 3-Col
Math Truth

Turing 1936
Non-Deterministic Poly-Time (NP)

Computable

Exp

Poly

Known
GCD

NP
3-Col
Games

CoNP
Not 3-Col
Halting
Math Truth

Acceptable

If the program does halt,
I can give you its computation
as a witness.
It the statement
does have a proof,
I could give you a proof
as a witness.
Non-Deterministic Poly-Time (NP)

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

Computable

Exp

Poly

Known
GCD

NP
Definition is asymmetric.
There is a witness that
a graph has a 3-Col.
There is no known witness that
a graph has no 3-Col.
3-Col

CoNP
Not 3-Col

Jack Edmonds

Steve Cook
NP vs Co-NP Preserving Reductions

GIVEN:
Not 3-Col

BUILD:
3-Col

Yes
G is not 3-colorable

No
G is not 3-Colorable
3-Col ≤poly Not 3-Col
NP vs Co-NP Preserving Reductions

GIVEN:
Not 3-Col

BUILD:
3-Col

No
G is 3-colorable

Yes
G is 3-Colorable
3-Col ≤poly Not 3-Col
If poly time
Not poly time
Poly time
If not poly time

NP vs Co-NP Preserving Reductions

GIVEN:
Not 3-Col

BUILD:
3-Col

No
G is 3-colorable

Yes
G is 3-Colorable
3-Col ≤poly Not 3-Col
???
If NP-complete

NP vs Co-NP Preserving Reductions

Computable

Exp

Poly

Known
GCD

NP
Definition is asymmetric.
There is a witness that
a graph has a 3-Col.
There is no known witness that
a graph has no 3-Col.
3-Col

CoNP
Not 3-Col

Jack Edmonds

Steve Cook
???
If NP-complete

NP vs Co-NP Preserving Reductions

Palg ≤poly Poracle
Cook Reduction:
Design any fast algorithm for Palg using a
supposed fast algorithm for Poracle as a subroutine.
Karp Reduction:
The algorithm for Palg calls that for Poracle only once
Yes  Yes & No  No

NP vs Co-NP Preserving Reductions

We will only consider reductions of this simple form.
Because they preserve NP vs Co-NP

Palg ≤poly Poracle
Karp Reduction:
Yes  Yes
& No  No
NP vs Co-NP Preserving Reductions

Computable

Exp

Poly

Known
GCD

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

Computable

Exp

Poly

Known
GCD

complete
NP-Complete Problems
Problem Pnew is NP-Complete
Pnew not too hard.
Pnew  NP
Pnew sufficiently hard.
PNP, P ≤poly Pnew
Easier: Sat ≤poly Pnew
Cook: P ≤poly Sat
Pnew
Sat

Clique: Given , does G contains a k-clique?

A K-independent set
is a set of K nodes
with no edges between them.

Independent Set: Given , does G contains a k-Ind Set?
K-Clique vs K-Independent Set
A K-clique is a set of K nodes
with all edges between them.

Clique: Given , does G contains a k-clique?

Independent Set: Given , does G contains a k-Ind Set?
K-Clique vs K-Independent Set
Brute Force: Try out all n choose k possible subsets.
If k = (n) then 2(n) subsets to check
If k=3 then
only O(n3)

GIVEN:
Indep. Set Oracle

BUILD:
Clique
Oracle

G* has a k Indep. set
or not

G has a k clique
or not
Clique ≤poly Indep Set
K-Clique vs K-Independent Set

GIVEN:
Indep. Set Oracle

BUILD:
Clique
Oracle

G* has a k Indep. set
or not

G has a k clique
or not
Clique ≤poly Indep Set
Proof of correctness:
Our oracle says yes to
iff Old oracle says yes to
iff G* has a k indep. set
iff G has a k clique

K-Clique vs K-Independent Set

G*
G
G* has edge
if and only if
G does not
K-Clique vs K-Independent Set

G*
G
This graph contains a clique
of size 4.

This graph contains an independent set of size 4.

if and only if
K-Clique vs K-Independent Set

Steps for proving that Pnew is NP-Complete
1) I am addicted to solving NP-Complete Problems
2) I trust in my higher power to help

A witness
12 Steps

Steps for proving that Pnew is NP-Complete
0) Pnew  NP
1) What to reduce it to
2) What is what
3) Direction of reduction & Code
4) Look for similarities
5) Instance Map
6) Solution Map
7) Valid to Valid
8) Reverse Solution Map
9) Valid to Valid
10) Working Algorithm
11) Running Time

12 Steps

Formal definition:
Pnew  NP iff  poly time Valid
such that Pnew(I) =  S Valid(I,S)
Design poly-time algorithm Valid(I,S)
which determines whether a given solution S
is valid for a given instance I.
12 Steps
Step 0: Pnew  NP

Palg ≤poly Poracle
Choose a problem Pis NP-comp
that is as similar to Pnew as possible and
that is already known to be NP-Complete.
12 Steps
Step 1: What to reduce it to

44
..

= Independent Set
= Clique
Pnew
Pis NP-comp
Inew
Iis NP-comp

k=4

k=3
Snew
Sis NP-comp

12 Steps
Step 2: What is what

45
..

Reduce Pnew to Pis NP-comp or Pis NP-comp to Pnew?
Pis NP-comp ≤poly Pnew
Palg ≤poly Poracle

12 Steps
Step 3: Direction of reduction & Code

46
..

12 Steps
Step 3: Direction of reduction & Code

47
..

Independent Set
Clique
Both instances are graphs: nodes & edges
A clique solution is a subset of the nodes with edges.
An Ind Set solution is a subset of the nodes without edges.

12 Steps
Step 4: Look for similarities

48
..

12 Steps
Step 5: Instance Map

49
..

Ioracle = InstanceMap(Ialg)
Ialg
12 Steps
Step 5: Instance Map

Ioracle
Ialg

no
yes

Yes mapped to Yes
No to No
12 Steps
Step 5: Instance Map

12 Steps
Step 6: Solution Map

52
..

Ioracle
Ialg
Potential Solution S.

Potential Solution
= SolutionMap(S).

12 Steps
Step 6: Solution Map

Salg = SolutionMap(Soracle)
Ioracle = InstanceMap(Ialg)
Ialg
Soracle

If Soracle is valid
solution for Ioracle,
then Salg is valid
solution for Ialg
Valid
Valid

12 Steps
Step 7: Valid to Valid

Ioracle
Ialg
Potential Solution S.

Potential Solution
= ReverseSolutionMap(S).

12 Steps
Step 8: Reverse Solution Map
Not part of code,
but of proof.

Salg
Ioracle = InstanceMap(Ialg)
Ialg

Soracle = ReverseSolutionMap(Salg)

If Salg is valid
solution for Ialg,
then Soracle is valid
solution for Ioracle
Valid
Valid

12 Steps
Step 9: Valid to Valid

Our Algalg says yes to Ialg
iff old Algoracle says yes to Ioracle
iff Ioracle has a valid solution Soracle
iff Ialg has a valid solution Salg
iff Ialg is a yes instance.

Steps 6&7

Steps 8&9
12 Steps
Step 10: Working Algorithm

57
..

Salg = SolutionMap(Soracle)
Ioracle = InstanceMap(Ialg)
Algalg(Ialg) is poly time if
the following are poly time:

Algoracle(Ioracle)
Assumed
Your job

12 Steps
Step 11: Running Time

Graph
Colouring
Scheduling

Clique
Independent Set

Palg ≤poly Poracle
or Palg Poracle

Circuit
Satisfiability

Any NP-Problem

This will prove that
Cir-SAT is NP-Complete.

GIVEN:
Oracle for Cir-Sat

BUILD:
Oracle for arbitrary
NP Problem
?

I don’t even know what problem I am trying to solve!!!
Reduction
Any NP-problem ≤poly Cir-SAT

We have a poly-time alg Valid(I,S) to test
whether or not S is a valid solution for I.

k=4
Valid
Formal definition:
Parbitrary  NP iff  poly time Valid
such that Parbitrary(I) =  S Valid(I,S)
We need to solve some unknown NP-Problem.
What do we know about it?

GIVEN:
Oracle for Cir-Sat

BUILD:
Oracle for arbitrary
NP Problem
Please, give me
a solution S
such that
Valid(I,S) is true.

Reduction
Any NP-problem ≤poly Cir-SAT

That looks like
a Turing Machine.
I only know about
circuits

The Circuit Satisfiability Problem
x3
x2
x1
OR
OR
AND
AND
OR
NOT
One bit output
No feedback
An instance is a circuit C.
F
T
F

A solution is an assignment X = [F,T,F…].
F
F
F
F
F
T
C(X) evaluates to T or F.

The Circuit Satisfiability Problem
x3
x2
x1
OR
OR
AND
AND
OR
NOT
An instance is a circuit C.

A solution is an assignment X = [F,T,F…].
A valid solution has C(X) = True.
F
F
F
F
F
T
F
T
F
Given a circuit,
does it have a
satisfying assignment?

Very Powerful
Turing (and friends) prove that
any algorithm computed by a
JAVA program in poly-time
can be computed by a
Turing Machine in poly-time.
Cook proves that any algorithm
computed by a Turing Machine
in time T(n) can be computed
by a family of circuits of size [T(n)]2.

But clearly, circuits compute.
The Circuit Satisfiability Problem

GIVEN:
Oracle for Cir-Sat

BUILD:
Oracle for arbitrary
NP Problem
Please, give me
a solution S
such that
VI(S) is true.

Reduction
Any NP-problem ≤poly Cir-SAT

Thanks for the circuit.
But what is S?
I can only find
assignments.
I build a circuit VI(S)
equivalent to Valid(I,S)

GIVEN:
Oracle for Cir-Sat

BUILD:
Oracle for arbitrary
NP Problem
Please, give me
an assignment X
such that
VI(X) is true.

Reduction
Any NP-problem ≤poly Cir-SAT

My pleasure.
Here: X
I build a circuit VI(S)
equivalent to Valid(I,S)

I decode X into S
and am done.

12 Step Program
Let’s be more formal.
And flow the 12 steps.

Step 0: Cir-SAT  NP
Design poly-time algorithm ValidCir-SAT(C,X)
which determines whether a given assignment X
is valid for a given circuit C.
Easy: Evaluate C(X).

Step 1: What to reduce it to
Palg ≤poly Cir-Sat
Choose a problem Pis NP-comp
that is as similar to Cir-Sat as possible and
that is already known to be NP-Complete.
Any NP-problem ≤poly Cir-SAT

Have none.

We have a poly-time alg Valid(I,S) to test
whether or not S is a valid solution for I.

70
..

Step 2: What is what
= Circuit-Sat
= some NP problem
Pnew
Parbitrary
Inew
Iarbitrary
Snew
Sarbitrary
= I
= S
x3
x2
x1
OR
OR
AND
AND
OR
NOT
F
F
F

71
..

Step 3: Direction of reduction & Code
Given oracle for Cir-Sat,
we need to be able to solve any NP-Complete problem.

Cir-Sat

Parbitrary

72
..

I
S
x3
x2
x1
OR
OR
AND
AND
OR
NOT
F
F
F
Step 4: Look for similarities
?

73
..

Step 5: Instance Map

74
..

Step 5: Instance Map
I  circuit
We have a poly-time alg Valid(I,S) to test
whether or not S is a valid solution for I.

Let Validn(I,S) be a circuit:
I is a bit string representing an instance I.
S is a bit string representing a solution S.
Outputs T if S is an encoding of a valid solution of I.

G,k

And over pairs of nodes

{u.v}  E OR uS OR vS

Eg: Clique
|S|  k

Step 5: Instance Map

Outputs T if
S is an encoding of
a valid solution S of I
I
S
I  circuit

hard wired
Given an instance I
Circuit VI(S) = Valid(I,S)

Validn(I,S)

VI(S)

Step 6: Solution Map

77
..

Step 6: Solution Map
S  assignment

X is viewed as a bit string S representing a solution S.
If X is not a bit string
representing a solution
then “what ever”
X=[T,F,F,T,F,T]

Outputs T if
S is an encoding of
a valid solution S of I
I
S

hard wired

VI(S)

Step 6: Solution Map
S  assignment

X is viewed as a bit string S representing a solution S.
X=[T,F,F,T,F,T]

Outputs T if
S is an encoding of
a valid solution S of I
I
S

hard wired

VI(S)

solution S

Step 7: Valid  Valid
VI(X) = T

Outputs T if
S is an encoding of
a valid solution S of I
I
S

hard wired

VI(S)

Valid(I,S) = Validn(I,S) = VI(X) = T
S is a valid solution of I.

Step 8: Rev. Sol. Map
solution  assignment

S bit string representing a solution S
solution S

X=[T,F,F,T,F,T]

Outputs T if
S is an encoding of
a valid solution S of I
I
S

hard wired

VI(S)

Step 9: Valid  Valid

Outputs T if
S is an encoding of
a valid solution S of I
I
S

hard wired

VI(S)
S is a valid solution of I.
VI(X) = T

VI(X) = Validn(I,S) = Valid(I,S) = T

GIVEN: Alg for circuit problem

BUILD:
Opt.
problem

satisfiable
or not

Yes/No
Reduction

VI
i.e.  S, S is a valid solution for I
i.e.  X, VI(X)
Any NP-problem ≤poly Cir-SAT

Graph
Colouring
Scheduling

Clique
Independent Set

Palg ≤poly Poracle
or Palg Poracle

Circuit
Satisfiability

Any NP-Problem

3-Col

3-Col
Graph Col: Given graph G & k
can G be coloured with k colours?
3-Col: Given graph G
can G be coloured with 3 colours?
3-Col ≤poly Graph Col
If you can decide whether you can colour with k colours,
then you can decide whether you can colour with 3 colours.

G,k

Graph
Colouring
Scheduling

Clique
Independent Set

Palg ≤poly Poracle
or Palg Poracle

Circuit
Satisfiability

Any NP-Problem

3-Col

3-SAT

3-SAT
Cir Sat: Given circuit C
does it have a satisfying assignment X?
3-SAT: Given an expression:
A circuit consisting of a big AND of clauses
Each clause is the OR of at most 3 literals
Each literal is a variable or its negation.
does it have a satisfying assignment X?

xoryorz AND xorwora AND …

F
T
T

F
F
F
F
T
T

F
F
F

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

3-SAT
Cir Sat: Given circuit C
does it have a satisfying assignment X?
3-SAT: Given an expression:
does it have a satisfying assignment X?

xoryorz AND xorwora AND …

F
T
T

F
F
F
F
T
T

F
F
F
3-Sat ≤poly Cir Sat
If you can decide whether any circuit is satifiable,
then you can decide whether a circuit that happens to be
an expression is satisfiable.

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

Graph
Colouring
Scheduling

Clique
Independent Set

Palg ≤poly Poracle
or Palg Poracle

Circuit
Satisfiability

Any NP-Problem

3-SAT
3-Col

Graph Col ≤poly Cir SAT
»
3-Col ≤poly 3-SAT

Step 5: Instance Map
Graph G  Expression V
Given an instance G
Circuit VG(C) = Valid(G,C)

Outputs T if
C is an encoding of
a valid 3-colouring C of G

hard wired

Encoding C of C:
u is a node
r is a colour
x = T
if node u is colour r.

Step 5: Instance Map
Graph G  Expression V
Given an instance G
Circuit VG(C) = Valid(G,C)

hard wired

Encoding C of C:
u is a node
r is a colour
x = T
if node u is colour r.
And over edges and colours r

x = F OR x = F
clauses with 2 literals

Step 5: Instance Map
Graph G  Expression V
Given an instance G
Circuit VG(C) = Valid(G,C)

hard wired

Encoding C of C:
u is a node
r is a colour
x = T
if node u is colour r.
And over node u

clauses with 3 literals

x =T OR x=T OR x=T

GIVEN: Alg for circuit problem

BUILD:
Opt.
problem

satisfiable
or not

Yes/No
Reduction

VG
i.e.  C, C is a valid 3-colouring for G
i.e.  X, VG(X)
3-Col ≤poly 3-SAT

Graph
Colouring
Scheduling

Clique
Independent Set

Palg ≤poly Poracle
or Palg Poracle

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

?
This will prove that 3-Col is NP-Complete.
And so are Scheduling,
Graph-Colouring, and
3-SAT.

Given a circuit,
find a satisfying assignment.

Steve Cook 1971
SAT is NP-Complete!

Computable

Exp

Poly

Known
GCD

NP
SAT

complete
Sat ≤poly 3-Col

Colour each node
with 3 colours.
Nodes with lines between them must have different colours.
»
Two problems that are cosmetically different, but substantially the same

Given a circuit,
find a satisfying assignment.
Circuit Satisfiablity ≤poly 3-Col
This will prove that 3-Col is NP-Complete.
Sat ≤poly 3-Col

Step 0: 3-Col  NP
Design poly-time algorithm Valid3-Col(G,C)
which determines whether a given 3-colouring C
is valid for a given graph G.
Easy: Check that each edge is bi-chromatic.

Step 1: What to reduce it to
Palg ≤poly 3-Col
Choose a problem Pis NP-comp
that is as similar to 3-Col as possible and
that is already known to be NP-Complete.
Pis NP-comp = Cir-SAT

98
..

Step 2: What is What
Circuit Problem:
instance = circuit
of gates
solution = true/false
to each variable
3-Colouring
instance = graph

solution = green/red/blue
to each node.
OR
OR

NOT
Output
x
y
z
G

Col

F
T
T

GIVEN: Alg for
3-colour
problem

BUILD:
Alg for circuit problem

Given an oracle for
3-colorability, how can you quickly solve circuit SAT?
Step 3: Direction of reduction & Code

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
Reduction
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

Step 4: Look for Similarities

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?

Graph Colouring

Colour each node.
Nodes with lines between them must have different colours.

Graph Colouring
Yes.
How do we know?

Because we colored it!
Could you do it
with 3 colours?

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
Y
Output
F
F
X Y Out
F F
F T
T F
T T

F
F

X Y Or
F F
F T
T F
T T

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

x
y
Output
F
F
F

T
F
X
Output
X NOT
F T
T F

NOT – Gadget

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
Reduction
Circuit ≤poly 3-Colouring

Step 5: Instance Map

119
..

Step 5: Instance Map
circuit  graph
OR
OR

NOT
x
y
z
Output

variables&wires
~ nodes
Step 5: Instance Map
circuit  graph
OR
OR

NOT
x
y
z
Output

x
y
z

Output

Step 5: Instance Map
circuit  graph
OR
OR

NOT
x
y
z
Output

x
y
z

Output
One pallet for
“defining” truth.

gate ~ gadget

Step 5: Instance Map
circuit  graph
OR

NOT
OR

x
y
z
Output

x
y
z

Output

first input
second input
output
The Graph Named
“OR-Gadget”
gate ~ gadget

Step 5: Instance Map
circuit  graph
OR

NOT
OR

x
y
z
Output

x
y
z

Output

first input
second input
output

gate ~ gadget

Step 5: Instance Map
circuit  graph

x
y
z

Output

OR
OR

NOT
x
y
z
Output
output
input
The Graph Named
“NOT-Gadget”
gate ~ gadget

Step 5: Instance Map
circuit  graph

x
y
z

Output

OR
OR

NOT
x
y
z
Output
output
input

gate ~ gadget

Step 5: Instance Map
circuit  graph

x
y
z

Output

NOT
OR

x
y
z
Output
first input
second input
output
The Graph Named
“OR-Gadget”
gate ~ gadget

Step 5: Instance Map
circuit  graph

x
y
z

Output

NOT
OR

x
y
z
Output
first input
second input
output

gate ~ gadget

One extra edge
from “False”
to “Output”
Step 5: Instance Map
circuit  graph
OR
OR

NOT
x
y
z
Output

Step 5: Instance Map
circuit  graph
OR
OR

NOT
x
y
z
Output
Done

x
y
z

F
F
T

Output
OR
OR

NOT
x
y
z
Output
Step 6: Solution Map
assignment  colouring

T
F

Assume these are
the colours
of these nodes.

OR
OR

NOT
x
y
z

x
y
z

F
Output
Output
Step 7: Valid  Valid

T
F
correspond

correspond

F
F
T

OR Gadget

OR
OR

NOT
x
y
z

x
y
z

Output
Output

T
F
F

correspond

Not Gadget
correspond

Step 7: Valid  Valid
F
F
T

OR
OR

NOT
x
y
z

x
y
z

Output
Output

T
F
correspond

OR Gadget
Step 7: Valid  Valid
F
F
T

F
F
correspond

OR
OR

NOT
x
y
z

x
y
z

F
F

Output
Output

T
F
One extra edge
from “False”
to “Output”
Oops this is
a bad coloring
Step 7: Valid  Valid
F
F
T

x
y
z

F
T
T

Output
OR
OR

NOT
x
y
z
Output
Step 6: Solution Map
assignment  colouring

T
F

Assume these are
the colours
of these nodes.

OR
OR

NOT
x
y
z

x
y
z

F
T
T

T
Output
Output
Step 7: Valid  Valid

T
F
correspond

correspond

T
correspond

OR
OR

NOT
x
y
z

x
y
z

F
T
T

T
F

Output
Output

T
F
One extra edge
from “False”
to “Output”
T
Can’t be F
Step 7: Valid  Valid

OR
OR

NOT
x
y
z

x
y
z

F
T
T

T
F

Output
Output

T
F
T
T
correspond

Must be T
valid colouring

satisfying assignment

Step 7: Valid  Valid

OR
OR

NOT
x
y
z

x
y
z

F
T
T

Output
Output
Step 8: Rev. Sol. Map
assignment  colouring

Rest of colouring
follows

OR
OR

NOT
x
y
z

x
y
z

F
T
T

Output
Output

Step 9: Valid  Valid

Edges in Gadgets
bi-chromatic

OR
OR

NOT
x
y
z

x
y
z

F
T
T

Output
Output

Extra Edge?
correspond

Step 9: Valid  Valid
T
valid
Must be T
Extra Edge
bi-chromatic

OR
OR

NOT
x
y
z

x
y
z

F
T
T

Output
Output

Step 9: Valid  Valid
T
valid
satisfying assignment

valid colouring

OR
OR

NOT
x
y
z

x
y
z

F
T
T

Output
Output

Satisfiability of this circuit
=
3-colourability of this graph
Step 5-9
F
T
T
T

Satisfiability of this circuit
=
3-colourability of this graph

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
Reduction
Circuit ≤poly 3-Colouring

Graph
Colouring
Scheduling

Clique
Independent Set

Palg ≤poly Poracle
or Palg Poracle

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

This proves that 3-Col is NP-Complete.
And so are Scheduling,
Graph-Colouring, and
3-SAT.

Graph
Colouring
Scheduling

Clique
Independent Set

Palg ≤poly Poracle
or Palg Poracle

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

?
True but we will not do this here.

Graph
Colouring
Scheduling

Clique
Independent Set

Palg ≤poly Poracle
or Palg Poracle

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

NP-Complete Problems
If we can solve one of these quickly,

then we can solve all NP-problems quickly.

Palg ≤poly Poracle
or Palg Poracle

Graph
Colouring
Scheduling

Clique
Independent Set

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

NP-Complete Problems
If we can prove one takes exponential time,

then all NP-complete problems take exponential time.

Network Flows

?
Yes: If we can solve Sat fast,
we can solve Network Flow fast,
because we can solve Network Flow fast.
Graph
Colouring
Scheduling

Clique
Independent Set

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

NP-Complete Problems

No: We can solve Network Flow fast,
but we cannot solve Sat fast.
?

Network Flows
Graph
Colouring
Scheduling

Clique
Independent Set

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

NP-Complete Problems

Yes: We use the fast alg
for Network Flow
to give a fast alg
for Bipartite Matching.

Network Flows

?
Bipartite Matching
Graph
Colouring
Scheduling

Clique
Independent Set

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

NP-Complete Problems

Math Truth

Network Flows

Bipartite Matching
Halting problem poly Math Truth
 Math Truth  Undecidable.
Graph
Colouring
Scheduling

Clique
Independent Set

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

NP-Complete Problems

Math Truth

Yes: If we can solve
Math Truth fast,
we can solve Sat fast.

Network Flows

Bipartite Matching
Undecidable

Graph
Colouring
Scheduling

Clique
Independent Set

Circuit
Satisfiability

Any NP-Problem

3-SAT

3-Col

NP-Complete Problems

Steps for proving that Pnew is NP-Complete
Designed after collecting lots of wrong answers.
Understand and follow them carefully.
Keep the steps separate, because errors happen when they are intertwined.
12 Steps
In More Detail

Steps for proving that Pnew is NP-Complete
1) Pnew  NP
2) What is what
3) Direction of reduction & Code
4) Look for similarities
5) Instance Map
6) Solution Map
7) Valid to Valid
8) Reverse Solution Map
9) Valid to Valid
10) Working Algorithm
11) Running Time

12 Steps
In More Detail

Reduce Pnew to Pis NP-comp or Pis NP-comp to Pnew?
People get this wrong.
Don’t memorize it. Go through it each time.
I want to prove Pnew is hard
hence that Pis NP-comp poly Pnew
hence that Pis NP-comp is easy
hence I need to design an algorithm for Pis NP-comp
hence I start with an input instance Iis NP-comp for Pis NP-comp
to get help, I must map it to an instance Inew for Pnew
Pis NP-comp ≤poly Pnew
Palg ≤poly Poracle

12 Steps
Step 3: Direction of reduction & Code

158
..

Step 5 Ioracle = InstanceMap(Ialg)
Steps 6,7: Salg = SolutionMap(Soracle)
Steps 8,9: Soracle = ReverseSolutionMap(Salg)

Palg
Ialg
Salg
Poracle
Ioracle
Soracle
≤poly

12 Steps
If and Only If
Not part of code,
but of proof.

Algoracle says yes to Ioracle
Ioracle has a valid solution Soracle
Ialg has a valid solution Salg
Ialg is a yes instance.

Steps 6&7
12 Steps
If and Only If
Algoracle says no to Ioracle
Ioracle does not have a valid solution Soracle
Ialg does not have a valid solution Salg
Ialg is a no instance.
No witness
to map!
Take to contra positive.
Algoracle gives the correct answer
Our algorithm gives the correct answer.
(whether yes or no)

160
..

Algoracle says yes to Ioracle
Ioracle has a valid solution Soracle
Ialg has a valid solution Salg
Ialg is a yes instance.

Steps 6&7
12 Steps
If and Only If
Algoracle says yes to Ioracle
 Ioracle has a valid solution Soracle
 Ialg has a valid solution Salg
 Ialg is a yes instance.

Steps 8&9
Algoracle gives the correct answer
Our algorithm gives the correct answer.
(whether yes or no)
Take to contra positive.

161
..

Salg = SolutionMap(Soracle)
Ioracle = InstanceMap(Ialg)
Ialg
Soracle

Every solution Soracle
needs to be considered.
Not just those you
intended when you
created I oracle.

12 Steps
Wider net

Ioracle = InstanceMap(Ialg)
Ialg
Potential Solution S.

To be safe,
cast a bigger net.

Potential Solution
= SolutionMap(S).

12 Steps
Wider net

It is best to separate the steps of
defining the entire solution Salg being mapped to
in a well defined and clear way.
the proof that Salg is a valid solution.

A false proof
defines part of Salg
proves that this makes some aspect of Salg valid.
Later to make some other aspect of Salg valid,
it redefines the same part of Salg in an inconsistent way.

12 Steps
Wider net and Separate steps 6 & 7

12 Steps
Step 5: Instance Map

165
..

Ioracle
Ialg

no
yes

ok mapped
to twice

ok not mapped to
Yes mapped to Yes
No to No
12 Steps
Step 5: Instance Map

Ioracle
Ialg

no
yes

InstanceMap
does not know if
Ialg is a Yes
instance.
12 Steps
Step 5: Instance Map

Ioracle
Ialg

no
yes

InstanceMap
does not know if
Ialg is a Yes
instance.

A useful mapping
but not poly-time.
12 Steps
Step 5: Instance Map

Ioracle
Ialg
Potential Solution S.

Potential Solution
= SolutionMap(S).

12 Steps
Forward vs Reverse Solution Map

Ioracle
Ialg
Potential Solution S.

Potential Solution
= ReverseSolutionMap(S).

12 Steps
Forward vs Reverse Solution Map

Soracle
Salg

Salg = SolutionMap(Soracle)
Soracle = ReverseSolutionMap(Salg)

In this case, bijective
12 Steps
Forward vs Reverse Solution Map

Soracle
Salg

Salg = SolutionMap(Soracle)

ok mapped
to twice
ok not mapped to

Soracle = ReverseSolutionMap(Salg)

Even the unexpected solutions
need to be mapped.
12 Steps
Forward vs Reverse Solution Map

The End

An early version of these slides produced by
Steven Rudich
from Carnegie Mellon University

Things Cut Out
of More Detailed NP Talk

Computational Complexity Theory
Computational Complexity Theory is the study of how much of a given resource (such as time, space, parallelism, randomness, algebraic operations, communication, or quantum steps) is required to perform the computations that interest us the most.

Given a graph G, what is a fast algorithm to decide if it can be 2-colored?

2 CRAYOLAS
PERSPIRATION; BRUTE FORCE:
Try out all 2n ways of 2 coloring G.

Sorry

Things Cut Out
of intro theory talk

Boss assigns task:
Given a computer program, will it halt?

Everyday industry asks these questions.

Example: Halting Problem
loop a = 1 … 1,000,000
s := s+a
end loop
loop a > 0
s := s+a
end loop
Halts
Does not halt

Example: Halting Problem
loop a,b,c,z > 2
exit when az + bz = cz
end loop
Proof of not halting =
Proof of
Fermat’s Last Theorem
loop
chaotic behavior
exit when
special event
end loop
Chaotic behavior =
not knowing what it will do without doing it.
How can we know it will not halt without running it forever?

Your answer:
Sorry. No algorithm exists that tells you for every computer program whether it halts!

Suppose there was a working algorithm:
Halt(P,I) = whether program P halts on input I
Construct from it another algorithm:
Nhalt(P) = if(Halt(P,P)) loop forever else halt
= halts ↔ program P does not halt on input P.
Paradox: Nhalt(Nhalt) = ?
program Nhalt halts on input Nhalt
↔
program Nhalt does not halt on input Nhalt
Contradiction!

Halting Problem

Your answer:
Sorry. No algorithm exists that tells you for every computer program whether it halts!

Or any other useful thing about what the program does.

Research in Computer Science

Vision
Graphics
Robotics
Systems
Data Bases
Networks
Real Time
Artificial Intelligence
Theory

Theoretical
Computer Science
Useful
Fun
Doable by you

So you want to be a computer scientist?

It is important to
learn theory!
Micro soft packages.
Programming

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

Everyday industry asks these questions.

Um? Tell me what to code.

The demand for mundane programmers is diminishing.
Your answer:

Your answer:
I learned this great algorithm that will work.
Soon all known algorithms
will be available in libraries.

Your answer:
I can develop a new algorithm for you.
Great thinkers
will always be needed.

Alternatively, your answer:
Sorry. Very likely no fast algorithm exists that always finds best schedule.

This too will
impress your boss.

(else worthy of wealth & Nobel prize)

The future belongs to the computer scientist who has

A large collection of tools to draw on.

Rudich www.discretemath.com

Creativity
The future belongs to the computer scientist who has

Logical Thinking
The future belongs to the computer scientist who has

Abstract thinking.

The future belongs to the computer scientist who has

It is important to
learn theory!

Theoretical
Computer Science
Research
Andy Mirzaian
Suprakash Datta
Franck Van Breugel
Jeff Edmonds
Patrick Dymond
Zbigniew Stachniak
Joseph Liu
George Tourlakis
Eric Ruppert

Theoretical Computer Science at York

Complexity Theory
Algorithms for solving problem
Determining time and memory used
Proving can’t do better

Theoretical Computer Science at York

Many machines working together
Different speed clocks
Different memory and programs
Communication Networks
Parallel Algorithms

Theoretical Computer Science at York

Other Topics
Large-scale scientific computing
Sparse matrix technology
Computational geometry
Combinatorial optimization
Graph algorithms
Computational logic,
Knowledge representation

Some Typical Ideas in
Theoretical Computer Science

Computer Science
Started with Theory
The theory of computation and algorithms was developed well before the hardware was invented.
This is one of the reasons that progress was made so fast when the hardware was developed.

Please feel free to ask questions!
Professors at York
are accessible.

A Hotdog

A combination of pork, grain, and sawdust, …

Constraints:
Amount of moisture
Amount of protean,
…

The Hotdog Problem

Given today’s prices,
what is a fast algorithm
to find the cheapest hotdog?

There are deep ideas within the simplicity.

=
Abstraction
Goal: Understand and think about complex things in simple ways.
There are deep ideas within the simplicity.
Rudich www.discretemath.com

Abstract Out Essential Details
Cost: $29, $8, $1, $2
Amount to add: x1, x2, x3, x4
pork
grain
water
sawdust
3×1 + 4×2 – 7×3 + 8×4 ³ 12
2×1 – 8×2 + 4×3 – 3×4 ³ 24
-8×1 + 2×2 – 3×3 – 9×4 ³ 8
x1 + 2×2 + 9×3 – 3×4 ³ 31
Constraints:
moisture
protean,
…
29×1 + 8×2 + 1×3 + 2×4
Cost of Hotdog:

3×1 + 4×2 – 7×3 + 8×4 ³ 12
2×1 – 8×2 + 4×3 – 3×4 ³ 24
-8×1 + 2×2 – 3×3 – 9×4 ³ 8
x1 + 2×2 + 9×3 – 3×4 ³ 31
29×1 + 8×2 + 1×3 + 2×4
Subject to:
Minimize:
Abstract Out Essential Details

A Fast Algorithm
For decades people thought that there was no fast algorithm.

Then one was found!
Theoretical Computer Science
finds new algorithms every day.
3×1 + 4×2 – 7×3 + 8×4 ³ 12
2×1 – 8×2 + 4×3 – 3×4 ³ 24
-8×1 + 2×2 – 3×3 – 9×4 ³ 8
x1 + 2×2 + 9×3 – 3×4 ³ 31
29×1 + 8×2 + 1×3 + 2×4
Subject to:
Minimize:
»

Doable by You
How can I solve problems that smart people have worked hard on?

Doable by You
We will teach you how to do it.
You will come upon new problems that no one has thought about before.
Hence, you will have the first chance to solve them.

Think

Be Creative

Theoretical Computer Science

Gauss
S = 1 + 2 + 3 + . . . + n
Arithmetic Sum
Rudich www.discretemath.com

1 2 . . . . . . . . n
= number of white dots.

1
+
2
+
3
+
. . .
+
n-1
+
n
=
S

1
+
2
+
3
+
. . .
+
n-1
+
n
=
S
n
+
n-1
+
n-2
+
. . .
+
2
+
1
=
S

1 2 . . . . . . . . n
= number of white dots
= number of yellow dots

n . . . . . . . 2 1

1
+
2
+
3
+
. . .
+
n-1
+
n
=
S
n
+
n-1
+
n-2
+
. . .
+
2
+
1
=
S
= number of white dots
= number of yellow dots
n+1 n+1 n+1 n+1 n+1
n
n
n
n
n
n
= n(n+1) dots in the grid

2S dots

Perspiration Search
Try all possible combinations
to find the cheapest
Too many to try.
With 50 ingredients,
number of valid combinations is more than the number of atoms.

2
1)(nn
S



/docProps/thumbnail.jpeg

Related Posts