Unit of Study Surveys
The University of Sydney
Page 1
Open 28 October Anonymous
Please fill these out, so we can improve the course using your feedback
Feel free to comment on the course, lecturer, tutors, anything that went right or wrong
If commenting on a person, please mention that person by nameSurvey is anonymous, so we dont know who your tutor is
Practice Exam
The University of Sydney
Page 2
Yes, there will be a practice exam put on Canvas No answers will be provided
Post your solution on Ed if you want feedback
Week 13 Announcement
The University of Sydney
Page 3
No lecture
Ill have office hours 8 November 57pm regular lecture time in the School of Computer Science J12, room 411
This is for questions about the course material
If you plan to come by, itd be great if you can let me know beforehand
Do you want a tutorial in week 13?
Result: Yes, there will be a tutorial.
NP and Computational Intractability
The University of Sydney
Page 4
Recap: Asymptotic Growth
Functions
55lognlogn5n525nn! The University of Sydney
Page 5
Factorial
Exponential
Polynomial
Poly Logarithmic
Logarithmic Constant
Algorithms and hardness
Algorithmic techniques:
Greedy algorithms
DivideConquer algorithms
Dynamic programming algorithmsNetwork flow algorithms
Hardness:
NPhardness: Onc algorithm is unlikely
Undecidability: No algorithm possible Halting problem
The University of Sydney
Page 6
Outline of todays lecture
Reduction:polynomialtime
Reduction by simple equivalence.
Reduction from special case to general case.
Reduction by encoding with gadgets.Definition of P and NP
NPcompleteness
Copingwithhardness
The University of Sydney
Page 7
Classify Problems According to Computational Requirements
Question: Which problems will we be able to solve in practice? A working definition. Cobham 1964, Edmonds 1965, Rabin 1966.
Those with polynomialtime algorithms.
Yes
Probably no
Shortest path
Longest path
Matching
3Dmatching
Min cut
Max cut
2SAT
3SAT
Planar 4color
Planar 3color
Bipartite vertex cover
Vertex cover
The University of Sydney
Page 8
Classify Problems
Aim: Classify problems according to those that can be solved in polynomialtime and those that cannot.
Frustrating news: Huge number of fundamental problems have defied classification for decades.
This lecture: Show that these fundamental problems in the grey area are computationally equivalent and appear to be different manifestations of one hard problem.
The University of Sydney Page 9
PolynomialTime Reductions
The University of Sydney Page 10
PolynomialTime Reduction
Suppose we could solve problem Y in polynomial time. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
The University of Sydney Page 11
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Example: Transitive closure of a directed graph can be computed by n calls to BFSthe time to build the transitive
closure.
abcd The University of Sydney a b c d
Page 12
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Input to TC
GV,E
The University of Sydney
Page 13
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Input to TC
GV,E
Transforms instance for X to instances for Y
The University of Sydney
Page 14
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Solves Y
f1X
f2X
fnX
Input to TC
GV,E
Solves Y
The University of Sydney
fiXG,vi
Page 15
Transforms instance for X to instances for Y
Solves Y
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Solves Y
f1X
f2X fnX
Solves Y
Input to TC
GV,E
Solves Y
Transforms instance for X to instances for Y
The University of Sydney
fiXG,vi
Solution to Y vertices reachable
from v on input fiX. i
Page 16
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Solves Y Solves Y
fnX
fiXG,vi
Merge info into GTCG
Solution to Y vertices reachable
from v on input fiX. i
Input to TC
GV,E
f1X f2X
The University of Sydney
Page 17
Transforms instance for X to instances for Y
Solves Y
Transform solutions for Y to a solution for X
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Input to TC
GV,E
f1X f2X
fnX
fiXG,vi
Solves Y Solves Y
Solves Y
Merge info into GTCG
Output for TC
G
Transforms instance for X to instances for Y
Transform solutions for Y to a solution for X
The University of Sydney
Solution to Y vertices reachable
from v on input fiX. i
Page 18
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Reduction time?
Input to TC
On
The University of Sydney
Solves Y
f1X
f2X fnX
Output for TC
Transforms instance for X to instances for Y
Solves Y
Solves Y
nTimeY
On2
Transform solutions for Y to a solution for X
Solution to Y on input fiX.
TCP BFS
Page 19
PolynomialTime Reduction
Suppose we could solve problem Y in polynomialtime. What else could we solve in polynomial time?
Reduction. Problem X polynomial reduces to problem Y, denoted XP Y, if arbitrary instances of problem X can be solved using:
Polynomial number of standard computational steps, plus
Polynomial number of calls to an oracle that solves problem Y.
Solves Y
f1X
Input
to X f2X
fkX
The University of Sydney kOnc
Output for X
Transforms instance for X to instances for Y
Solves Y
Solves Y
Transform solutions for Y to a solution for X
Solution to Y on input fiX.
Page 20
PolynomialTime Reduction
Purpose. Classify problems according to relative difficulty.
1. Design algorithms. If XP Y and Y can be solved in polynomialtime, then X can also be solved in polynomial time.
2. Establish intractability. If XP Y and X cannot be solved in polynomialtime, then Y cannot be solved in polynomial time.
Establish equivalence: If X P Y and Y P X, then X oP Y.
The University of Sydney Page 21
Reductions we have already seen
Transitive closure reduces to breadthfirst searchBipartite matching reduces to max flow
Max flow reduces to min cut
Circulation reduces to max flow
Circulation with lower bounds reduces to circulation… Sorting reduces to convex hull not discussed
The University of Sydney
Page 22
Reduction By Simple Equivalence
The University of Sydney
Page 23
Basic reduction strategies.
Reduction by simple equivalence.
Reduction from special case to general case.Reduction by encoding with gadgets.
Independent Set
INDEPENDENTSET: Given a graph GV, E and an integer k, is there a subset of vertices S I V such that S 3 k, and for each edge at most one of its endpoints is in S?
There is no blue node adjacent to another blue
The University of Sydney
Page 24
We will study decision problems
Decision problem:
Does there exist an independent set of size 3 k?
Search problem: Find an independent set of maximum cardinality. Selfreducibility: Search problemP decision version.
Applies to all problems in this lecture.
Justifies our focus on decision problems.
Example: to find maximum cardinality independent set.
Binary search for cardinality k of maximum independent set.
The University of Sydney
Page 25
Independent Set
INDEPENDENTSET: Given a graph GV, E and an integer k, is there a subset of vertices S I V such that S 3 k, and for each edge at most one of its endpoints is in S?
Ex. Is there an independent set of size 3 6? Yes. Ex. Is there an independent set of size 3 7? No.
independent set
The University of Sydney Page 26
Vertex Cover
VERTEXCOVER: Given a graph GV, E and an integer k, is there a subset of vertices S I V such that Sk, and for each edge, at least one of its endpoints is in S?
The University of Sydney Page 27
Vertex Cover
VERTEXCOVER: Given a graph GV, E and an integer k, is there a subset of vertices S I V such that Sk, and for each edge, at least one of its endpoints is in S?
Ex. Is there a vertex cover of size4? Yes. Ex. Is there a vertex cover of size3? No.
The University of Sydney
Page 28
Art gallery problem: place guardscctv within an art gallery so that all corridors are visible at any time
vertex cover
Vertex Cover and Independent Set
Theorem: VERTEXCOVER oP INDEPENDENTSET. VC P IS and IS P VC
The University of Sydney
Page 29
Vertex Cover and Independent Set
Theorem: VERTEXCOVER oP INDEPENDENTSET. VC P IS and IS P VC Proof: We show S is an independent set iff VS is a vertex cover.
independent set vertex cover
The University of Sydney
Page 30
Vertex Cover and Independent Set
Theorem: VERTEXCOVER oP INDEPENDENTSET. VC P IS and IS P VC Proof: We show S is an independent set iff VS is a vertex cover.
Let S be any independent set.
Consider an arbitrary edge u, v.
SindependentuISorvISuIVSorvIVS.Thus, VS covers u, vVS vertex cover.
U Let VS be any vertex cover.
ConsidertwonodesuISandvIS.
Observe that u, v I E since VS is a vertex cover.
Thus, no two nodes in S are joined by an edgeS independent set.
IS P VC
uv uv
VC P IS uv
The University of Sydney
Page 31
Not Examined
Reduction from Special Case to General Case
The University of Sydney
Page 32
Basic reduction strategies.
Reduction by simple equivalence.
Reduction from special case to general case.Reduction by encoding with gadgets.
Set Cover
SETCOVER: Given a set U of elements, a collection S1, S2, . . . , Sm of subsets of U, and an integer k, does there exist a collection of k of these sets whose union is equal to U?
Sample application.
m available pieces of software.
Set U of n capabilities that we would like our system to have.
The ith piece of software provides the set Si I U of capabilities.Goal: achieve all n capabilities using fewest pieces of software.
Example:
U 1, 2, 3, 4, 5, 6, 7k2
S1 3,7
S2 3,4,5,6 S3 1
S4 2,4
S5 5
S61,2,6,7
The University of Sydney
Page 33
Set Cover
SETCOVER: Given a set U of elements, a collection S1, S2, . . . , Sm of subsets of U, and an integer k, does there exist a collection of k of these sets whose union is equal to U?
Sample application.
m available pieces of software.
Set U of n capabilities that we would like our system to have.
The ith piece of software provides the set Si I U of capabilities.Goal: achieve all n capabilities using fewest pieces of software.
Example:
U 1, 2, 3, 4, 5, 6, 7k2
S1 3,7
S2 3,4,5,6
S3 1
S4 2,4
S5 5
S61,2,6,7
The University of Sydney
Page 34
Vertex Cover Reduces to Set Cover
Theorem: VERTEXCOVER P SETCOVER.
Proof: Given a VERTEXCOVER instance GV, E, k, we construct a set cover
instance whose size equals the size of the vertex cover instance.
Construction.
Create SETCOVER instance:
kk, UE, Sv eIE:eincidenttov
Setcover of sizek iff vertex cover of sizek.
VERTEX COVER
ab
e7 e2 e3 e4
f e6 c
k2
e1
e5
ed
SET COVER
U 1, 2, 3, 4, 5, 6, 7
k2
Sa3, 7
Sc3, 4, 5, 6 Se1
Sb2, 4
Sd5
Sf 1, 2, 6, 7
The University of Sydney
Page 35
Vertex Cover Reduces to Set Cover
Theorem: VERTEXCOVER P SETCOVER.
Proof: Given a VERTEXCOVER instance GV, E, k, we construct a set cover
instance whose size equals the size of the vertex cover instance.
Construction.
Create SETCOVER instance:
kk, UE, Sv eIE:eincidenttov
Setcover of sizek iff vertex cover of sizek.
VERTEX COVER
ab
e7 e2 e3 e4
f e6 c
k2
e1
e5
ed
SET COVER
U 1, 2, 3, 4, 5, 6, 7
k2
Sa3, 7
Sc3, 4, 5, 6 Se1
Sb2, 4
Sd5
Sf 1, 2, 6, 7
The University of Sydney
Page 36
Reductions via Gadgets
The University of Sydney
Page 37
Basic reduction strategies.
Reduction by simple equivalence.
Reduction from special case to general case.Reduction by encoding with gadgets.
Satisfiability
Literal: A Boolean variable or its negation. Clause: A disjunction of literals.
Conjunctive normal form CNF: A propositional formula F that is the conjunction of clauses.
xi or xi
Cjx1 U x2 U x3
F C1UC2UC3UC4 SAT: Given CNF formula F, does it have a satisfying truth assignment?
3SAT: SAT where each clause contains exactly 3 literals.
Given:x1 U x2 U x3Ux1 U x2 U x3Ux2 U x3Ux1 U x2 U x3 Return: true since x1true, x2true, x3false is a satisfying assignment
The University of Sydney Page 38
3Satisfiability Reduces to Independent Set
Theorem: 3SAT P INDEPENDENTSET.
INDEPENDENTSET: Given a graph GV, E and an integer k, is there a subset of vertices S I V such that S 3 k, and for each edge at most one of its endpoints is in S?
The University of Sydney Page 39
3Satisfiability Reduces to Independent Set
Theorem: 3SAT P INDEPENDENTSET.
Proof: Given an instance F of 3SAT, we construct an instance G, k of
INDEPENDENTSET that has an independent set of size k iff F is satisfiable. Construction.
G contains 3 vertices for each of the k clauses, one for each literal.Connect 3 literals in a clause in a triangle.
Connect literal to each of its negations.
G, k3
x1 x2 x1
The University of Sydney
x2 x3 x1 x3 x2 x4 Fx1 Ux2 Ux3Ux1 Ux2 Ux3Ux1 Ux2 Ux4
Page 40
Not Examined
3Satisfiability Reduces to Independent Set
Claim. G contains independent set of size kF iff F is satisfiable.
Proof:Let S be independent set of size k.
S must contain exactly one vertex in each triangle.
Set these literals to true.
Truth assignment is consistent and all clauses are satisfied.
G, k3
x1 x2 x1
The University of Sydney
x2 x3 x1 x3 x2 x4 Fx1 Ux2 Ux3Ux1 Ux2 Ux3Ux1 Ux2 Ux4
Page 41
Not Examined
3Satisfiability Reduces to Independent Set
Claim. G contains independent set of size kF iff F is satisfiable.
Proof:Let S be independent set of size k.
S must contain exactly one vertex in each triangle.
Set these literals to true.
Truth assignment is consistent and all clauses are satisfied.
Proof: U Given satisfying assignment, select one true literal from each triangle. This is an independent set of size k.
G, k3
x1 x2 x1
The University of Sydney
x2 x3 x1 x3 x2 x4 Fx1 Ux2 Ux3Ux1 Ux2 Ux3Ux1 Ux2 Ux4
Page 42
Not Examined
Clique
A clique of a graph G is a complete subgraph of G. Every two distinct vertices in the clique are adjacent
clique of size 4
clique of size 3
CLIQUE: Given a graph GV,E and an integer k, does GV,E contain a clique of size k?
The University of Sydney Page 43
Satisfiability Reduces to Clique
Theorem: SAT P CLIQUE.
Idea:
Make column for each of the k clauses.
No edge within a column.
All other edges present except between x and x.
The University of Sydney
Page 44
Satisfiability Reduces to Clique
Example:
G
Ex U y U z U x U y U z Uy U z
x y
z
x
y
z
y
Observation: G has a kclique, if and only if E is satisfiable.
The University of Sydney
Page 45
z
Not Examined
Reduction Review
Basic reduction strategies.
1. Simple equivalence: INDEPENDENTSET oP VERTEXCOVER.
2. Special case to general case: VERTEXCOVER P SETCOVER.
3. Encoding with gadgets: 3SAT P INDEPENDENTSET.
3SAT P CLIQUE
Transitivity. If X P Y and Y P Z, then X P Z.
Proof idea: Compose the two algorithms.
Example: 3SAT P INDEPENDENTSET P VERTEXCOVER P SETCOVER.
The University of Sydney
Page 46
Definition of NP
Class P
Class NP
Class NPcomplete
The University of Sydney
Page 47
Definition of the class P
Class P: Decision problems for which there is a polytime algorithm.
Problem
Description
Algorithm
Yes
No
MULTIPLE
Is x a multiple of y?
Grade school division
51, 17
51, 16
RELPRIME
Are x and y relatively prime?
Euclid 300 BCE
34, 39
34, 51
PRIMES
Is x prime?
AKS 2002
53
51
RNA secondary structure
Is there an RNA secondary structure of weight at most 3?
Dynamic programming
accgguagu
aaaaggggg
MST
Is there a MST of weight 5?
Prims
The University of Sydney Page 48
Definition of the class NP
Class NP: Decision problems for which there is a non deterministic, polynomial time algorithm.
E.g. if we had a nondeterministic Turing Machine, then we could solve them in polynomial time. Our usual model of computing is equivalent to deterministic Turing Machines.
Intuitionimagine we had a computer which could explore all of the possible solutions simultaneously.
We will look at a more practical definition next!
The University of Sydney Page 49
Definition of the class NP
Certification algorithm intuition.
Certifier views things from managerial viewpoint.
Certifier does not solve the problem on its own;
rather, it checks if a proposed proof t is a valid solution.
Definition: Algorithm Cs,t is a certifier for problem X if for every input instance s and proposed proof t, Cs, tyes if and only if t is a valid solution to X.
certificate or witness
Class NP: Decision problems for which there exists a polytime certifier.
The University of Sydney Page 50
Certifiers and Certificates: Set Cover
SETCOVER: Given a set U of elements, a collection S1, S2, . . . , Sm of subsets of U, and an integer k, does there exist a collection of k of these sets whose union is equal to U?
Certificate: tSi1, Si2, …, Sik Certifier:
boolean Cs,t
if the number of setsk
return false elseifvIU:v I asetint
return true
else
return false
Example: U1,2,3,4, S11, S22,3, S31,4 and k2 certificate tS2,S3
Conclusion: SETCOVER is in NP. The University of Sydney
Page 51
Certifiers and Certificates: 3Satisfiability
SAT: Given a CNF formula F, is there a satisfying assignment? Certificate: An assignment of truth values to the n boolean variables. Certifier: Check that each clause in F has at least one true literal.
x1 Ux2 Ux3Ux1 Ux2 Ux3Ux1 Ux2 Ux4Ux1 Ux3 Ux4 instance s
Conclusion: 3SAT is in NP. The University of Sydney
Page 52
x1,x2,x4true, x3false certificate t
Certifiers and Certificates: Hamiltonian Cycle
HAMCYCLE: Given an undirected graph GV, E, does there exist a simple cycle C that visits every node?
Certificate: ta permutation of the n nodes.
Certifier: Check that the permutation contains each node in V exactly once, and that there is an edge between each pair of adjacent nodes in the permutation.
Conclusion: HAMCYCLE is in NP.
instance s certificate t
The University of Sydney Page 53
P, NP
P: Decision problems for which there is a polytime algorithm. NP: Decision problems for which there is a polytime certifier.
Claim: P I NP.
The University of Sydney Page 54
P, NP, EXP
P: Decision problems for which there is a polytime algorithm.
NP: Decision problems for which there is a polytime certifier.
EXP: Decision problems for which there is an exponentialtime algorithm.
Claim: P I NP. Claim: NP I EXP.
The University of Sydney Page 55
The Main Question: P Versus NP
Is PNP? Cook 1971, Edmonds, Levin, Yablonski, Godel
Is the decision problem as easy as the certification problem?
One of the seven Millennium Prize problems: 1 million prize if solved.
EXP
P NP
If P1NP
EXP
PNP
If PNP
would break RSA cryptography
PNP: P1NP:
Efficient algorithms for 3COLOR, TSP, FACTOR, SAT, …
No efficient algorithms possible for 3COLOR, TSP, SAT, …
Consensus opinion on PNP? Probably no. The University of Sydney
Page 56
NPCompleteness
The University of Sydney Page 57
Class NPComplete
NPcomplete: A problem Y in NP with the property that for every problem X in NP, XpY.
Theorem: Suppose Y is an NPcomplete problem. Then Y is solvable in polytime iff PNP.
Proof:
U If PNP then Y can be solved in polytime since Y is in NPP.Suppose Y can be solved in polytime.
LetXbeanyprobleminNP. SinceXp Y,wecansolveXin polytime. This implies NP I P.
WealreadyknowP I NP.ThusPNP.
The University of Sydney
Page 58
Circuit Satisfiability
CIRCUITSAT. Given a combinational circuit built out of AND, OR, and NOT gates, is there a way to set the circuit inputs so that the output is 1?
output
Yes: 101
NOT
U AND
U U
U OR
CIRCUITSAT I NP U OR
The University of Sydney
Page 59
10??? hardcoded inputs inputs
The First NPComplete Problem
Theorem: CIRCUITSAT is NPcomplete. Cook 1971, Levin 1973 Proof: main idea
Any algorithm that takes a fixed number of bits n as input and produces a yesno answer can be represented by such a circuit. Moreover, if algorithm takes polytime, then circuit is of polysize.
Proof not part of the course.
The University of Sydney
Page 60
Establishing NPCompleteness
Remark: Once we establish first natural NPcomplete problem, others fall like dominoes.
Recipe to establish NPcompleteness of problem Y.Step1. ShowthatYisinNP.
Step 2. Choose an NPcomplete problem X.Step 3. Prove that Xp Y.
Justification: If X is an NPcomplete problem, and Y is a problem in NP with the property that XP Y then Y is NPcomplete.
Proof: LetWbeanyprobleminNP. ThenW P X P Y.Bytransitivity,WP Y.
Hence Y is NPcomplete.The University of Sydney
by definition of NPcomplete
by assumption
Page 61
3SAT is NPComplete
Theorem. 3SAT is NPcomplete.
Proof: Suffices to show that CIRCUITSATP 3SAT since 3SAT is in NP.
Let K be any circuit.
Create a 3SAT variable xi for each circuit element i.
Make circuit compute correct values at each node:
x2 U x3 , x2 U x3
x1 x4 Ux5add3clauses: x1Ux4, x1Ux5 , x1Ux4 U x5
x2 x3add2clauses:
x0x1Ux2 add3clauses: x0Ux1, x0Ux2,x0Ux1Ux2
Hardcoded input values and output value.x5 0add1clause: x5
x0 1add1clause: x0
Final step: turn clauses of length3 into clauses of length exactly 3.
x0
U U
x1
x2
x5 x4
x3
The University of Sydney
Page 62
0??
Not Examined
Using transitivity
3SAT is NPcomplete
3SAT P INDEPENDENTSET P VERTEXCOVER P SETCOVER
Corollary:
INDEPENDENTSET, VERTEXCOVER and SETCOVER are NPcomplete.
The University of Sydney
Page 63
Some NPComplete Problems
Six basic genres of NPcomplete problems and paradigmatic examples.
Packing problems: SETPACKING, INDEPENDENT SET.Covering problems: SETCOVER, VERTEXCOVER.
Constraint satisfaction problems: SAT, 3SAT.
Sequencing problems: HAMILTONIANCYCLE, TSP.Partitioning problems: 3DMATCHING, 3COLOR.
Numerical problems: SUBSETSUM, KNAPSACK.
The University of Sydney
Page 64
More Hard Computational Problems
Aerospace engineering: optimal mesh partitioning for finite elements.
Biology: protein folding.
Chemical engineering: heat exchanger network synthesis.
Civil engineering: equilibrium of urban traffic flow.
Economics: computation of arbitrage in financial markets with friction.
Electrical engineering: VLSI layout.
Environmental engineering: optimal placement of contaminant sensors.
Financial engineering: find minimum risk portfolio of given return.
Game theory: find Nash equilibrium that maximizes social welfare.
Genomics: phylogeny reconstruction.
Mechanical engineering: structure of turbulence in sheared flows.
Medicine: reconstructing 3D shape from biplane angiocardiogram.
Operations research: optimal resource allocation.
Physics: partition function of 3D Ising model in statistical mechanics.
Politics: ShapleyShubik voting power.
Pop culture: Minesweeper consistency.
Statistics: optimal experimental design.
The University of Sydney
Page 65
Not Examined
Games
The Eternity II puzzle, is a puzzle competition which was released in 2007.
A 2 million prize was offered for the first complete solution.
The Eternity II puzzle is an edgematching puzzle which involves placing 256 square puzzle pieces into a 16 by 16 grid, constrained by the requirement to match adjacent edges.
The problem is NPcomplete.
The competition ended at noon on 31 December 2010, with no solution being found.
The University of Sydney
Page 66
Not Examined
Class NPhard
Class NPcomplete: A problem in NP such that every problem in NP polynomial reduces to it.
Class NPhard:
A decision problem such that every problem in NP reduces to it. not necessarily in NP
The University of Sydney Page 67
Many classes?
The University of Sydney Page 68
Not Examined
Numerical Problems
The University of Sydney
Page 69
Six Basic genres
Packing problems: SETPACKING, INDEPENDENT SET.Covering problems: SETCOVER, VERTEXCOVER.
Constraint satisfaction problems: SAT, 3SAT.
Sequencing problems: HAMILTONIANCYCLE, TSP.
3SAT P DIR HAMILTONIAN CYCLE P HAMILTONIAN CYCLE P TSPPartitioning problems: 3DMATCHING, 3COLOR.
Numerical problems: SUBSETSUM, KNAPSACK.
Numerical Problems
SUBSETSUM: Given a set S of n integers v1, …, vn, and a target value t, is there a nonempty subset S I S such that the elements in S sum to exactly t?
Example:3,6,7,2,4,3,t10.Yes
KNAPSACK: Given a set of n items, each with weight wi and value vi, can a
value of at least q be achieved without exceeding the weight W?
The University of Sydney Page 70
Vertex Cover Reduces to Subset Sum
Theorem: VERTEXCOVER P SUBSETSUM.
Proof: Given an instance G, k of VERTEXCOVER, construct an instance S, t of SUBSETSUM that has a subset of S summing to t iff G has a vertex cover of size at least k.
The University of Sydney Page 71
Vertex Cover Reduces to Subset Sum
Proof: Given an instance G, k of VERTEXCOVER, construct an instance S, t of SUBSETSUM that has a subset of S summing to t iff G has a vertex cover of size at least k.
Number edges from 0 to E1. Set S of integers:
For the ith edge, add an integer bi
For each vertex v, add an integer av
bi4i
av4EX 4i
i:ith edge is incident to v EX1
tk4E24i The University of Sydney i0
Page 72
Vertex Cover Reduces to Subset Sum
Proof: Given an instance G, k of VERTEXCOVER, construct an instance S, t of SUBSETSUM that has a subset of S summing to t iff G has a vertex cover of
size at least k.
Number edges from 0 to E1. Set S of integers:
For the ith edge, add an integer bi
For each vertex v, add an integer av
bi4i
av4EX 4i
0 xyz
1
tk4E
The University of Sydney i0
24i
Page 73
i:ith edge is incident to v
az1104 ay1114
ax1014
EX1
t1224
k1
b00014
b10104
Vertex Cover Reduces to Subset Sum
Claim: G has vertex cover of size at most k iff S, t has a subset summing to t. Proof:Let C be a vertex cover of size exactly k.
Consider the subset of S
Xav :v2Cbi :edgeiiscoveredbyexactlyonevertexinC
The most significant digit is exactly kThe ith digit is exactly 2.
Therefore sum of X is exactly t
bi4i
av4EX 4i
i:ith edge is incident to v EX1
tk4E24i The University of Sydney i0
Page 74
Vertex Cover Reduces to Subset Sum
Claim: G has vertex cover of size at most k iff S, t has a subset summing to t. Proof: U Let X be a subset of S summing to t
Then there exists subsets V and E such that
X avX bik4EX 24i
E1 v2V 0 i2E0 i0
No carries in the first E digits
Each edge number bi contributes at most 1 to the ith digit of the sumSo, at least one of its endpoints must be in V
Thus, V is a vertex cover
bi4i
av4EX 4i i:ith edge is incident to v
The University of Sydney
Page 75
Sequencing Problems
The University of Sydney
Page 76
Six Basic genres
Packing problems: SETPACKING, INDEPENDENT SET.Covering problems: SETCOVER, VERTEXCOVER.
Constraint satisfaction problems: SAT, 3SAT.
Sequencing problems: HAMILTONIANCYCLE, TSP.
3SAT P DIR HAMILTONIAN CYCLE P HAMILTONIAN CYCLE P TSPPartitioning problems: 3DMATCHING, 3COLOR.
Numerical problems: SUBSETSUM, KNAPSACK.
Hamiltonian Cycle
HAMCYCLE: Given an undirected graph GV, E, does there exist a simple cycle G that contains every node in V.
The University of Sydney YES: vertices and faces of a dodecahedron. Page 77
Directed Hamiltonian Cycle
DIRHAMCYCLE: Given a directed graph GV, E, does there exists a simple directed cycle G that contains every node in V?
Theorem: DIRHAMCYCLEP HAMCYCLE.
Proof idea: Given a directed graph GV, E, construct an undirected graph
G with 3n vertices.
a
bv c
G
aout d
din
ein
e
bout cout
vin v vout
G
The University of Sydney
Page 78
Directed Hamiltonian Cycle
Claim: G has a Hamiltonian cycle iff G does.
Proof:
Then G has an undirected Hamiltonian cycle same order.
Suppose G has a directed Hamiltonian cycle G.
U
G must visit nodes in G using one of two orders:
Suppose G has an undirected Hamiltonian cycle G.
…, B, G, R, B, G, R, B, G, R, B, …
…, B, R, G, B, R, G, B, R, G, B, …
Blue nodes in G make up directed Hamiltonian cycle G in G, or reverse
of one.
aout
bout vin cout
din
ein
d dout
v vout G
The University of Sydney
Page 79
Not Examined
3SAT Reduces to Directed Hamiltonian Cycle
Theorem: 3SATP DIRHAMCYCLE.
Proof: Given an instance F of 3SAT, we construct an instance of DIRHAM
CYCLE that has a Hamiltonian cycle iff F is satisfiable.
General idea. First, create graph that has 2n Hamiltonian cycles which
correspond in a natural way to 2n possible truth assignments.
The University of Sydney
Page 80
Not Examined
3SAT Reduces to Directed Hamiltonian Cycle
Construction. Given 3SAT instance F with n variables xi and k clauses.For each clause: add a node and 6 edges.
C1 x1 Vx2 Vx3
clause node
clause node
s
The University of Sydney
Page 81
t
C2 x1 Vx2 Vx3
x1
x2
x3
Not Examined
Longest Path
SHORTESTPATH: Given a digraph GV, E, does there exists a simple path of length at most k edges?
LONGESTPATH: Given a digraph GV, E, does there exists a simple path of length at least k edges?
Theorem: 3SATP LONGESTPATH. Proof: not covered
The University of Sydney Page 82
Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function du, v, is there a tour of lengthD?
All 13,509 cities in US with a population of at least 500 Reference: http:www.tsp.gatech.edu
The University of Sydney
Page 83
Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function du, v, is there a tour of lengthD?
Optimal TSP tour
Reference: http:www.tsp.gatech.edu
The University of Sydney
Page 84
Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function du, v, is there a tour of lengthD?
11,849 holes to drill in a programmed logic array Reference: http:www.tsp.gatech.edu
The University of Sydney
Page 85
Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function du, v, is there a tour of lengthD?
Optimal TSP tour
Reference: http:www.tsp.gatech.edu
The University of Sydney
Page 86
Travelling Salesperson Problem
TSP: Given a set of n cities and a pairwise distance function du, v, is there a tour of lengthD?
HAMCYCLE: given a graph GV, E, does there exists a simple cycle that contains every node in V?
Theorem: HAMCYCLEP TSP. Proof:
Given instance GV, E of HAMCYCLE, create n cities with distance
function
TSP instance has tour of lengthn iff G is Hamiltonian.
du,vii1 ifu,vIE i2 ifu,vIE
The University of Sydney Page 87
NPcomplete games and puzzles
Battleship
Candy Crush Saga
Donkey Kong
Eternity II
Generalized FreeCell
Lemmings
Minesweeper Consistency Problem
Pokemon
SameGame
Generalized Sudoku
Generalized Tetris
Rush Hour
Hex
Generalized Super Mario Bros
The University of Sydney
Page 88
Not Examined
PolynomialTime Reductions
constraint satisfaction
3SAT
Dick Karp 1972 1985 Turing Award
SUBSETSUM
SCHEDULING
INDEPENDENT SET
VERTEX COVER
SET COVER
packing and covering
DIRHAMCYCLE
HAMCYCLE
TSP
sequencing
GRAPH 3COLOR
PLANAR 3COLOR
The University of Sydney
Page 89
partitioning
numerical
3SAT reduces to INDEPENDENT SET
Summary
Polynomial time reductions
3SAT P DIR HAMILTONIAN CYCLE P HAMILTONIAN CYCLE P TSP 3SAT P INDEPENDENTSET P VERTEXCOVER P SETCOVER
Complexity classes:
P: Decision problems for which there is a polytime algorithm.
NP: Decision problems for which there is a polytime certifier. NPcomplete: A problem in NP such that every problem in NP polynomial
reduces to it.
NPhard: Class of decision problems which are at least as hard as the hardest problems in NP. Problems that are NPhard do not have to be elements of NP; indeed, they may not even be decidable.
The University of Sydney Page 90
Reviews
There are no reviews yet.