Round 10: Computationally more difficult problems

Material:

So far almost all of our algorithms have been rather efficient, having worst-case running times such as O(log2n), O(n), O(nlog2n), O((|E|+|V|)log2|V|) and so on. But there are lots of (practical!) problems for which we do not know any efficient algorithms. In fact, there are even problems that provably cannot be solved by computers. Here “solve by computers” means “to have an algorithm that in all the cases gives the answer and the answer is correct”. The proof that such problems exists and more about this topic can be found in the Aalto course CS-C2150 Theoretical Computer Science (5cr, periods III-IV).

Example

There is no algorithm that always decides whether a multivariate polynomial has integer-valued roots.

_images/intro-hasintroots.jpg

As a curiosity, the output to x3+y3+z3112 is marked with “?” in the figure because we do not currently (September 23, 2019) know whether the are integers x, y and z such that x3+y3+z3=112. The cases 33 and 42 were solved only in 2019, see this wikipedia article.

This round

  1. gives a semi-formal description for one important class of computationally hard but still solvable problems, called NP-complete problems, and

  2. provides some methods for attacking such problems in practise.

Definitions by using formal languages etc and most of the proofs are not covered, they are discussed more in the Aalto courses

  • ​ CS-C2150 Theoretical Computer Science, and

  • ​ CS-E4530 Computational Complexity Theory.

Computational problems

A computational problem consists of a description of what the possible inputs, called instances of the problem, are and what is the question that should be answered on such inputs. As an example, the problem of testing whether an integer is a prime number can be expressed as the following computational problem.

Definition: Primality problem

Instance: A positive integer x.

Question: Is x a prime number?

To solve this problem, one has to develop an algorithm that gives the correct answer for all possible input instances.

_images/intro-isprime.jpg

A problem is decidable (or “computable”, or sometimes “recursive” due to historical reasons) if there is an algorithm that can, for all possible instances, answer the question. For instance, the Primality problem is decidable; a simple but inefficient way to test whether x is a prime number is to check, for all integers i[2..x], that i does not divide x.

In a decision problem the answer is either “no” or “yes”.

Definition: The subset-sum problem

Instance: A set S of integers and a target value t.

Question: Does S have a subset SS such that sSs=t?

In a function problem the answer is either

  • ​ “no” when there is no solution, and

  • ​ a solution when at least one exists.

Definition: The subset-sum problem (function version)

Instance: A set S of integers and a target value t.

Question: Give a subset SS such that sSs=t if such exists.

Mathematically, a computational problem with a no/yes answer can be defined as the set of input strings for which the answer is “yes”. Problems with a more complex answers can be defined as (partial) functions. These formal aspects will be studied more in the Aalto course “CS-C2150 Theoretical computer science”.

In optimization problems one has to find an/the optimal solution.

Definition: minimum spanning tree problem

Instance: A connected edge-weighted and undirected graph G.

Question: Give a minimum spanning tree of the graph.

For an optimization problem there usually is a corresponding decision problem with some threshold value for the solution (is there an “at least this good solution”?).

Definition: minimum spanning tree (decision version) problem

Instance: A connected edge-weighted and undirected graph G and an integer k.

Question: Does the graph have a spanning tree of weight k or less?

The full optimization problem is at least as hard as this decision version because an optimal solution gives immediately the solution for the decision version as well.

In computational complexity theory, the set of decidable problems can be divided in many smaller complexity classes:

  • P — problems that can be solved in polynomial time ( always efficiently) with algorithms

  • NP — problems whose solution can be verified in polynomial time (or that can solved with non-deterministic machines in polynomial time)

  • PSPACE — problems that can be solved with a polynomial amount of extra space (possibly in exponential time)

  • EXPTIME — problems that can be solved in exponential time

  • ​ and many more…

_images/hierarchy.jpg

Polynomial-time solvable problems

A problem is polynomial-time solvable if there is an algorithm that solves the problem in time O(nc) for some constant c, where n is the length of the input instance in bits (or, equivalently, in bytes). We consider such problems to be efficiently solvable, or tractable. If a problem is not tractable, then it is intractable. The class of all decision problems that can be solved in polynomial time is denoted by P.

Note

Polynomial-time algorithms involve algorithms with running times such as Θ(n100). Such algorithms can hardly be considered as “efficient”. But such running times do not occur often and once a polynomial-time algorithm is found, it is in many cases further improved to run in polynomial-time with a quite small polynomial degree.

Based on the sorting algorithms round, we know how to sort an array of n elements in time O(nlog2n). Thus the following function problem can be solved in polynomial time:

Definition: median of an array problem

Instance: A sequence of integers.

Question: What is the median of the values in the sequence (“no” if the sequence is empty)?

… and the following decision version is in the class P:

Definition: median of an array (a decision version) problem

Instance: A sequence of integers and an integer k.

Question: Is the median of the values in the sequence k or more?

From the graph rounds we know how to efficiently compute shortest paths between the vertices in a graph. Thus the following problem belongs to P:

Definition: shortest path problem

Instance: an undirected graph G=(V,E), two vertices v,vV, and an integer k.

Question: Is there a path of length k or less from v to v?

However, for the longest path problem we do not know any polynomial-time algorithms:

Definition: longest simple path problem

Instance: an undirected graph G=(V,E), two vertices v,vV, and an integer k.

Question: Is there a simple path of length k or more from v to v?

Similarly, we know how to compute minimum spanning trees efficiently and the following problem is thus in P:

Definition: minimum spanning tree (decision version) problem

Instance: A connected edge-weighted and undirected graph G=(V,E,w) and an integer k.

Question: Does the graph have a spanning tree of weight k or less?

But when not all the vertices have to be included in the tree, we do not know any algorithm that would solve all the instances efficiently:

Definition: Minimum Steiner tree (decision version) problem

Instance: A connected edge-weighted and undirected graph G=(V,E,w), a set SV, and an integer k.

Question: Does the graph have a tree that spans all the vertices in S and has weight k or less?

Problems in NP (Non-deterministic Polynomial time)

There are two (and even more) equivalent ways to characterize the decision problems in the class NP:

  1. Problems that can be solved in polynomial time with non-deterministic (Turing) machines.

    Such non-deterministic machines can compute the same functions as our current CPUs in polynomial time. In addition, they can “branch” their computations into many “simultaneous” computations and return a solution if at least one of the branches finds a solution. They cannot be implemented with the current hardware but are rather a conceptual tool; more on non-determinism in the CS-C2150 TCS course.

  2. Problems for which the solutions (when they exist) are

    • ​ reasonably small (i.e., of polynomial size w.r.t. the input), and

    • easy to check (i.e., in polynomial time w.r.t. the input).

    However, the solutions are not necessarily easy to find (or to prove non-existent)!

We use the latter definition and call such a small, easy-to-check solution a certificate for the instance in question. Obviously, only the “yes” instances have certificates.

The subset-sum problem

As a first example, consider the subset-sum problem.

Definition: subset-sum

Instance: A set S of integers and a target value t.

Question: Does S have a subset SS such that sSs=t?

For each instance (S,t) with the “yes” answer (and for only those), a certificate is a set S of integers such that SS and vS=t. The set S is obviously of polynomial size w.r.t. the instance (S,t) as SS. On can also easily check in polynomial time whether the certificate is valid, i.e., whether it holds that (i) SS and (ii) vS=t. Thus the subset-sum problem is in the class NP.

Example

A certificate for the instance (S,t) with

  • S={2,7,14,49,98,343,686,2409,2793,16808,17206,117705,117993} and

  • t=138457

is S={2,7,98,343,686,2409,17206,117705}.

The instance (S,t) with S={2,7,14,49} and t=15 does not have a certificate and the answer for it is “no”.

Propositional satisfiability

Propositional formulas are built on

  • ​ Boolean variables, and

  • ​ connectives of unary negation ¬, binary disjunction and binary conjunction .

In Scala terms, the negation ¬ corresponds to the unary operation !, the conjunction to the binary operation &&, and the disjunction to ||. The difference is that in Scala, a Boolean variable always has a value (either true of false). Therefore, in Scala a Boolean expression (a && !b) || (!a && b) can be evaluated at any time point to some value. In the propositional formula level, a variable is like an unknown variable in mathematics: it does not have a value unless we associate one by some mapping etc. Thus the propositional formula (a¬b)(¬ab) cannot be evaluated unless we give values to a and b: an assignment τ for a formula ϕ is a mapping from the variables vars(ϕ) in the formula to B={false,true}. It satisfies the formula if it evaluates the formula to true. A formula is satisfiable if there is an assignment that satisfies it; otherwise it is unsatisfiable.

Example

The formula ((ab¬c)(a¬bc)(¬abc)(¬a¬b¬c))(abc) is satisfiable as the assignment τ={atrue,bfalse,ctrue} (among 2 others) evaluates it to true.

The formula (a)(¬ab)(¬bc)(¬c¬a) is unsatisfiable.

Definition: propositional satisfiability, sat

Instance: a propositional formula ϕ.

Question: is the formula ϕ satisfiable?

The propositional satisfiability problem can be understood as the problem of deciding whether an equation ϕ=true has a solution, i.e. deciding whether the variables in ϕ have some values so that the formula evaluates to true. The problem is in NP as we can use a satisfying assignment as the certificate:

  • ​ its size is linear in the number of variables in the formula, and

  • ​ evaluating the formula to check whether the result is true is easy.

To simplify theory and practice, one often uses certain normal forms of formulas:

  • ​ A literal is a variable xi or its negation ¬xi

  • ​ A clause is a disjunction (l1lk) of literals

  • ​ A formula is in 3-CNF (CNF means conjunctive normal form) if it is a conjunction of clauses and each clause has 3 literals over distinct variables. For instance, (x1¬x2x4)(¬x1¬x2x3)(x2¬x3x4) is in 3-CNF.

Definition: 3-cnf-sat

Instance: a propositional formula in 3-CNF.

Question: is the formula satisfiable?

Some other problems in NP

Definition: Travelling salesperson

Instance: An edge-weighted undirected graph G and an integer k.

Question: Does the graph have a simple cycle visiting all the vertices and having weight k or less?

_images/fitour.gif

Source: Univ. Waterloo

Definition: Generalized Sudokus

Instance: An n×n partially filled Sudoku grid (n=k2 for some integer k1).

Question: Can the Sudoku grid be completed?

_images/sudoku.jpg

Definition: longest simple path (decision version) problem

Instance: an undirected graph G=(V,E), two vertices v,vV, and an integer k.

Question: Is there a simple path of length k or more from v to v?

Definition: minimum spanning tree (decision version) problem

Instance: A connected edge-weighted and undirected graph G=(V,E,w) and an integer k.

Question: Does the graph have a spanning tree of weight k or less?

Definition: Minimum Steiner tree (decision version) problem

Instance: A connected edge-weighted and undirected graph G=(V,E,w), a set SV, and an integer k.

Question: Does the graph have a tree that spans all the vertices in S and has weight k or less?

And hundreds of others…

P versus NP

For polynomial-time solvable problems, the instance itself can act as the certificate because we can always compute, in polynomial time, the correct no/yes answer from the instance itself. Therefore, PNP. However, we do not know whether P=NP. In other words, we do not know whether it is always the case that if a solution is small and easy to check, is it always relatively easy to find it? Most people believe that PNP but no-one has yet been able to prove this (or that P=NP). We know efficient algorithms for many problems such as minimum spanning tree, shortest path, and so on. But we do not know any efficient algorithms for subset-sum, 3-cnf-sat, and hundreds of other (practically relevant) problems in NP, even though lots of extremely clever people have tried to find ones for decades.

NP-complete problems

The class NP contains both problems that are easy (those in the class P) as well as problems for which we do not currently know efficient algorithms (but whose solutions are small and easy to check). There is a special class of problems in NP called NP-complete problems. They have the property that if any of them can be solved in polynomial time, then all of them can. In a sense, they are the hardest problems in the class NP. And there are lots of such problems.

Definition: Polynomial-time computable reduction

A polynomial-time computable reduction from a decision problem B to a decision problem A is a function R from the instances of B to the instances of A such that for each instance x of B,

  • R(x) can be computed in polynomial-time, and

  • x is a “yes” instance of B if and only if R(x) is a “yes” instance of A.

Therefore, if we have

  • ​ a polynomial time reduction from B to A, and

  • ​ a polynomial-time algorithm solving A,

then we have a polynomial-time algorithm for solving B as well: given an instance x of B, compute R(x) and then run the algorithm for A on R(x).

Definition: NP-completeness

A problem A in NP is NP-complete if every other problem B in NP can be reduced to it with a polynomial-time computable reduction.

Therefore,

  • ​ if an NP-complete problem A can be solved in polynomial time, then all the problems in NP can, and thus

  • NP-complete problems are, in a sense, the most difficult ones in NP.

We do not know whether NP-complete problems can be solved efficiently or not.

_images/npc2.jpg

The Cook-Levin Theorem

The fact that NP-complete problems exist at all was proven by Cook and Levin in 1970’s.

Theorem: Cook 1971, Levin 1973

sat (and 3-cnf-sat) is NP-complete.

Soon after this, Karp [1972] then listed the next 21 NP-complete problems. Since then, hundreds of problems have been shown NP-complete. For instance, travelling salesperson, generalized Sudokus etc are all NP-complete. For incomplete lists, one can see

  • ​ Garey and Johnson, 1979: Computers and Intractability: A Guide to the Theory of NP-Completeness, or

  • this wikipedia page.

How to prove a new problem NP-complete?

Suppose that we are given a new problem C that we suspect to be NP-complete. To prove that C is indeed NP-complete, we have to

  1. show that it is in NP,

  2. take any existing NP-complete problem A, and

  3. reduce A to the new problem C.

Because polynomial-time reductions compose, the existence of the reduction S from the NP-complete problem A to C actually shows that C is also NP-complete: for any problem B in NP, we can now build a reduction from B to C by

  • ​ first reducing the instance x of B to an instance R(x) of A (such a reduction R exists because A is NP-complete), and

  • ​ then reducing the instance R(x) to the instance S(R(x)) of C. The instance x is a “yes” instance of B if and only if S(R(x)) is a “yes” instance of C.

As a consequence, if the new problem C can be solved in polynomial time, then so can A and all the other problems in NP.

_images/npc5.jpg

Usually, but not always, the first step of showing that the new problem is in NP, meaning that it has polynomial-sized certificates that can be verified in polynomial time, is easy. The real difficulty is to choose the NP-complete problem A carefully so that defining the polynomial-time reduction from A to C is as easy as possible.

Proving NP-completeness: an example

Consider the following problem:

Definition: recruiting strangers

INSTANCE: A social network of students and a positive integer K, where a social network consist of (i) a finite set of students and (ii) a symmetric, binary “knows” relation over the students.

QUESTION: is it possible to recruit K students so that none of these students knows each other?

Example

Consider the instance with the network drawn below and K=3. Is it possible to find 3 students so that none of them knows any of the others?

_images/independent.jpg

This instance is indeed a “yes” instance, the green vertices below show a solution. Is the solution the only one or are there others?

_images/independent2.jpg

This problem is in fact equivalent to a well-known graph problem called independent set:

Definition: independent set

INSTANCE: An undirected graph G=(V,E) and an integer K.

QUESTION: Is there an independent set IV, with |I|=K? (A set IV is an independent set if for all distinct u,wI, {u,w}E.)

The independent set problem is one of the classic NP-complete problems, let’s now show this fact with a semi-formal proof.

Theorem

independent set is NP-complete.

Proof sketch

We reduce from the 3-cnf-sat problem. We are given a 3-CNF formula ϕ=C1Cm with m clauses, each Ci=(li,1li,2li,3) having exactly three literals over distinct variables. We form the corresponding independent set instance by letting K=m and building the graph G as follows.

  • ​ For each clause Ci=(li,1li,2li,3), the graph contains the vertices vi,1, vi,2, and vi,3. Intuitively, the vertex vi,p corresponds to the literal li,p (either x or ¬x for some variable x) of the clause.

  • ​ There is an edge between two vertices vi,p and vj,q if and only if either

    • i=j, meaning that the vertices correspond literals in the same clause, or

    • li,p=x and lj,q=¬x (or vice versa) for some variable x.

The first edge condition above guarantees that only one of the vertices corresponding to literals in the same clause can be selected in an independent set. The second one guarantees that if we select a vertex corresponding to a literal x in the independent set, then we cannot include any vertex corresponding to the literal ¬x (and vice versa).

Suppose that ϕ is satisfied by a truth assignment τ. Then we can form the independent set I of size K=m as follows. For each clause Ci=(li,1li,2li,3), τ(li,p)=true for at least one literal in it because τ satisfied ϕ: select one of such literals and include the corresponding vertex in the graph in I. The set I has m elements as is an independent set because we selected only one vertex in each “clause triangle” and never selected a literal and its negation.

On the other hand, suppose that I is an independent set of size K=m. In this case, we can form a truth assignment τ that satisfies ϕ as follows. For each clause Ci=(li,1li,2li,3), the independent set must contain exactly one of the vertices vi,1, vi,2, and vi,3, otherwise it could not be of size m or an independent set. Select the literal l corresponding to that vertex and let τ(x)=true if l=x and τ(x)=false if l=¬x for a variable x. After done for all the clauses, the truth assignment satisfies each of the clauses. It may still have some variables that do not have a value, let them have the value false.

As a consequence:

  • ​ If ϕ is satisfiable, then G has an independent set of size K.

  • ​ If G has an independent set of size K, then ϕ is satisfiable.

  • ϕ is satisfiable if and only if G has an independent set of size K.

Because of the above theorem, If we could solve independent set in polynomial time, then we could solve sat and all other problems in NP in polynomial time as well.

Example: Reduction from 3-cnf-sat to independent set

Consider the 3-CNF formula ϕ=(x1x2x3)(¬x1¬x2¬x3)(¬x1x2x3).

The corresponding independent set problem instance consists of the graph G below and the independent set size requirement K=3:

_images/independent-from-cnf.jpg

The formula ϕ is satisfiable. For any satisfying truth assignment, such as τ={x1true,x2true,x3false}, we can get an independent set of size 3 by taking, for each “clause triangle”, one of the vertices that correspond to a literal that evaluates to true in that clause under the assignment. For instance, the red vertices in the graph below show one possibility for the assignment τ above.

_images/independent-from-cnf2.jpg

Conversely, from any independent set of size 3 in the graph, we obtain a truth assignment τ that satisfies the formula ϕ by letting τ(x)=true if a vertex with label x is in the independent set, and τ(x)=false otherwise. For instance, consider the independent set shown below in red. From this, we obtain the truth assignment τ={x1false,x2true,x3false} that satisfies ϕ.

_images/independent-from-cnf3.jpg

Example: NP-completeness of subset-sum

The subset-sum problem is in NP as we can easily check whether a set of numbers (i) is a subset of the given set of numbers, and (ii) adds to the target value t. We can show that subset-sum is NP-complete by reducing 3-cnf-sat to it. Suppose that we are given a CNF formula ϕ=C1Cm, where each clause Ci contains 3 literals over distinct variables. Let the variables occurring in ϕ be x1,,xn. We now build (in polynomial time) an instance (Sϕ,tϕ) of subset-sum so that

ϕ is satisfiable if and only if Sϕ has a subset summing to tϕ.

Therefore, if we could solve subset-sum in polynomial time, then we could solve 3-cnf-sat in polynomial time as well. The polynomial-time reduction works as follows.

  • ​ The numbers in Sϕ and tϕ are base-10 numbers consisting of n+m digits ˆx1ˆxnˆC1ˆCm.

  • ​ For each variable xi, the set Sϕ includes two numbers:

    • vi with the digit ˆxi=1 and the digits ˆCj=1 for each clause Cj containing the literal xi; the other digits are 0.

    • vi with the digit ˆxi=1 and the digits ˆCj=1 for each clause Cj containing the literal ¬xi; the other digits are 0.

  • ​ For each clause Cj, the set Sϕ has two numbers:

    • sj with the digit ˆCj=1 and the other digits 0.

    • sj with the digit ˆCj=2 and the other digits 0.

  • ​ The target value tϕ has

    • ​ the digit ˆxi=1 for each variable xi, and

    • ​ the digit ˆCj=4 for each clause Cj.

Example

Consider the 3-CNF formula ϕ=C1C2C3C4, where

  • C1=(x1x2¬x3)

  • C2=(x1¬x2x3)

  • C3=(¬x1x2x3)

  • C4=(¬x1¬x2¬x3)

Observe that an assignment satisfies the formula iff it assigns an even number of x1, x2 and x3 to true. The corresponding subset-sum instance (Sϕ,tϕ), where Sϕ={1001100,1000011,101010,100101,10110,11001,1000,2000,100,200,10,20,1,2} and tϕ=1114444, is shown below.

_images/dynprog-cnf-to-subsetsum-1.png

The subset S of Sϕ highlighted with green in the figure is a solution to (Sϕ,tϕ). The assignment τ={x1false,x2true,x3true} corresponding to S satisfies the formula ϕ.

The correctness of the reduction can be argumented as follows:

  1. Suppose that an assignment τ satisfies ϕ. We can build a corresponding SSϕ summing to tϕ as follows.

    • ​ First, for each variable xi: If τ(xi)=true for a variable xi, then include vi in S. Otherwise, include vi in S.

    • ​ At this point, the digit ˆCj in the sum is 1, 2, or 3.

    • ​ For each clause Cj, include the slack variable sj, sj or both so that the digit ˆCj in the sum becomes 4.

  2. In the other direction, suppose that a set SSϕ sums to tϕ. We build a truth assignment τ that satisfies ϕ as follows.

    • ​ First note that S contains either vi or vi (but not both) for each variable xi as the digit ˆxi=1 in tϕ.

    • ​ If viS, let τ(xi)=true, otherwise let τ(xi)=false.

    • ​ Now at least one literal in each clause Cj is true under τ because the slack variables sj alone can only sum the digit ˆCj up to 3 but 4 is required in tϕ.

NP-completeness: significance

Of course, the question of whether P=NP, or can NP-complete problems be solved in polynomial time, is a very important open problem in computer science. In fact, it is one of the seven (of which six are still open) one million dollar prize Clay Mathematics Institute Millennium Prize problems.

Because there are hundreds of NP-complete problems, the P=NP question has practical significance as well. As Christos Papadimitriou says in his book “Computational complexity”:

There is nothing wrong in trying to prove that an NP-complete problem can be solved in polynomial time. The point is that without an NP-completeness proof one would be trying the same thing without knowing it!

That is, suppose that you have a new problem for which you should develop an algorithm that is always efficient, i.e. runs in polynomial time. You may end up in trying really hard for very long time, probably without success, if the problem turns out to be NP-complete or harder. This is because during the last decades, lots of very clever people have tried to develop polynomial-time algorithms for many NP-complete problems, but no-one has succeeded so far.

So what to do when a problem is NP-complete? As there are lots practical problems that have to be solved even though they are NP-complete (or even harder), one has to develop some approaches that work “well enough” in practise. Some alternatives are:

  • ​ Develop backtracking search algorithms with efficient heuristics and pruning techniques.

  • ​ Attack some special cases occurring in practise.

  • ​ Develop approximation algorithms.

  • ​ Apply incomplete local search methods.

  • ​ Use existing tools.

Special cases

Sometimes we have a computationally hard problem but the instances that occur in practise are somehow restricted special cases. In such a case, it may be possible to develop an algorithm that solves such special instances efficiently. Technically, we are not solving the original problem anymore but a different problem where the instance set is a subset of the original problem instance set.

Example: subset-sum with smallish values

In the case of subset-sum, it is quite easy to develop a dynamic programming (recall Round 6) algorithm that works extremely well for “smallish” numbers. First, define a recursive function hasSubset(S,t) evaluating to true if and only if S={v1,v2,,vn} has a subset that sums to t:

  • hasSubset(S,t)=true if t=0,

  • hasSubset(S,t)=false if S= and t0,

  • hasSubset(S,t)=true if hasSubset({v2,v3,,vn},t)=true or hasSubset({v2,v3,,vn},tv1)=true, and

  • hasSubset(S,t)=false otherwise.

Now, using the memoization technique with arrays, it is easy to implement a dynamic programming algorithm that works in time O(|S|M) and needs O(Mlog2M) bytes of memory, where M=sS,s>0ssS,s<0s is the size of the range in which the sums of all possible subsets of S must be included. Solution reconstruction is also rather straightforward. Algorithm sketch:

  • ​ Take an empty array a.

  • ​ For each number xS in turn, insert in one pass

    • a[y+x]=x for each y for which a[y] is already defined, and

    • a[x]=x.

That is, in a number-by-number manner, insert all the subset sums that can be obtained either using the number alone or by adding it to any of the sums obtainable by using earlier numbers. The value written in the element a[s] tells what was the last number inserted to get the sum s; this allows reconstruction of the solution subset.

Example

Assume that the set of numbers is S={2,7,14,49,98,343,686,2409,2793,16808,17206,117705,117993}. The beginning of the array is

_images/dynprog-subsetsum.png

Inspecting the array, one can directly see that, for instance, there is a subset SS for which sS=58 and that such a subset is obtained with the numbers a[58]=49, a[5849]=a[9]=7 and a[97]=a[2]=2.

Is the dynamic programming algorithm above a polynomial time algorithm for the NP-complete problem subset-sum? No, unfortunately it is not:

  • ​ the size of the input instance is the number of bits needed to represent the numbers, and

  • ​ therefore the value of the sum sS,s>0ssS,s<0s, and thus the running time as well, can be exponentially large with respect to the instance size.

For instance, the numbers that were produced in our earlier reduction from 3-cnf-sat to subset-sum are not small: if the 3-cnf-sat instance has n variables and m clauses, then the numbers have n+m digits and their values are in the order 10n+m, i.e., exponential in n+m. Note: if the dynamic programming approach is implemented with hash maps instead of arrays, then it works for the special case when the numbers are not necessarily “smallish” but when the number of different sums that can be formed from S is “smallish”.

Reducing to an another problem

For some NP-complete and harder problems there are some very sophisticated solver tools that work extremely well for many practical instances:

Thus if one can reduce the current problem B into one of the problems A above, it may be possible to obtain a practically efficient solving method without programming the search method by one-self. Notice that here we are using reductions in the other direction compared to the case when we proved problems NP-complete: we now take the problem which we would like to solve and reduce it a problem for which we have an usually-efficient tool available:

_images/npc2.jpg

Example: solving Sudokus with SAT

Let us apply the above described approach to Sudoku solving. Our goal is to use the sophisticated CNF SAT solvers available. Thus, given an n×n partially filled Sudoku grid, we want to make a propositional formula ϕ such that

  • ​ the Sudoku grid has a solution if and only the formula is satisfiable, and

  • ​ from a satisfying assignment for ϕ we can build a solution for the Sudoku grid.

In practise we thus want to use the following procedure:

_images/flow-sudoku-cnf.png

To obtain such a CNF formula ϕ for a Sudoku grid, we first introduce a variable xr,c,v for each row r=1,,n, column c=1,,n and value v=1,,n. The intuition is that if xr,c,v is true, then the grid element at row r and column c has the value v. The formula ϕ=C1C2C3C4C5C6 is built by introducing sets of clauses that enforce different aspects of the solution:

  • ​ Each entry has at least one value: C1=1rn,1cn(xr,c,1xr,c,2xr,c,n)

  • ​ Each entry has at most one value: C2=1rn,1cn,1v<vn(¬xr,c,v¬xr,c,v)

  • ​ Each row has all the numbers: C3=1rn,1vn(xr,1,vxr,2,vxr,n,v)

  • ​ Each column has all the numbers: C4=1cn,1vn(x1,c,vx2,c,vxn,c,v)

  • ​ Each block has all the numbers: C5=1rn,1cn,1vn((r,c)Bn(r,c)xr,c,v) where Bn(r,c)={(rn+i,cn+j)0i<n,0j<n}

  • ​ The solution respects the given cell values H: C6=(r,c,v)H(xr,c,v)

The resulting formula has |H| unary clauses, n2n(n1)2 binary clauses, and 3n2 clauses of length n. Thus the size of the formula is polynomial with respect to n.

Example

Consider the following Sudoku grid:

_images/royle-plain.png

The corresponding CNF formula is: (x1,1,1x1,1,2x1,1,9)(x9,9,1x9,9,2x9,9,9)(¬x1,1,1¬x1,1,2)(¬x9,9,8¬x9,9,9)(x1,1,1x1,2,1x1,9,1)(x9,1,9x9,2,9x9,9,9)(x1,1,1x2,1,1x9,1,1)(x1,9,9x2,9,9x9,9,9)(x1,1,1x1,2,1x3,3,1)(x7,7,9x7,8,9x9,9,9)(x1,8,1)(x2,1,4)(x3,2,2)(x9,6,6) When the formula is given to a SAT solver, it declares that the formula has a model in which all x1,1,i except x1,1,6 are false, and so on. From the variables that are true, we obtain the following (unique) solution to the original Sudoku grid:

_images/royle-alldiff.png

An implementation of this approach, using the Sat4j SAT solver implemented in Java, is available in the Eclipse package for the “coloring with SAT” programming exercise. Feel free to compare its performance to the Sudoku solver you implemented in the CS-A1120 Programming 2 course.

Note

This approach of describing an instance of some other problem as a satisfiability instance, or an instance of some other similar constraint satisfaction formalism, is also called constraint programming.

It is a form of declarative programming: one only declares how the solution should look like and then a constraint solver finds one (or states that none exists).

Further references