Limits of
Computation
20 – Complete Problems Bernhard Reus
1
The story so far
• we have seen NP contains problems that seem intractable
• we don’t know whether P = NP
• we have defined NP-complete problems
(“hardest’’ problems in NP) • “angle” to analyse NP
2
20.1. SAT
“Hard” Problems in NP
• “the mother” of NP- complete problems (SAT)
• more examples of NP-
complete problems in all
areas of Computer
CHAPTER 20. COMPLETE PROBLEMS CHAPTER 20. COMPLETE PROBLEMS
Science (obtained via
reductions)
20.1. SAT
20.1 A First NP-complete Problem
http://www.cs.princeton.edu/~wayne/cs423/lectures/reductions-poly-4up.pdf
20.1 A First NP-complete Problem
So far we have seen results about NP-complete problems, but as far as we know,
there could still be no such NP-complete problem in the first place. Then we can
So far we have seen results about NP-complete problems, but as far as we know, apply the previous results to this problem in order to prove that other problems
there could still be no such NP-complete problem in the first place. Then we can are NP-complete as well. Note that we have carried out a similar task in the Com-
apply the previous results to this problem in order to prove that other problems putability section. It was first shown that the Halting Problem is undecidable and
are NP-complete as well. Note that we have carried out a similar task in the Com- then reduction was used to show that other problems are undecidable as well.
putability section. It was first shown that the Halting Problem is undecidable and The first concrete NP-complete problem we will encounter is about Boolean ex-
then reduction was used to show that other problems are undecidable as well. pressions (or formulae). Recall that a Boolean expression, or formula, is made up of
3
varTiahbelefisr,sbticnoanrycrceotenjNunPc-tcionmoppletreatporro^ble(m“anwde”)w, dililsejunnccotuionnteorpiserabtorut_B(o“olre”a)nanexd- purneasrsyionnesga(otirofnoormpeurlateo)r. ¬R.eAcanlletxhamt aplBeoiosl(exa^n eyx)p_re¬szs.ion, or formula, is made up of varRiaebclaelsl, tbhiantaarybcoonlejuancetxiopnreospsieornatFor ^is(c“laonsde”d),ifditsjhuanscntionvaorpiaebraletosrb_ut(v“aori”a)balensd uhnavaerybneegnarteiopnlaocpederbatyortr¬ut.hAvnaleuxeasm“ptrlueei”s a(xnd^“yf)a_lse¬”z.. A closed expression F can
B
e
o
o
l
a
n
E
x
vtraurie
Definition 20.1 (T1ruth assignment and evaluation). A truth assignment for F
abtya be eRveaclaulaltethd
flaeman
sionf BF
rait, ebif
a^blfe
tbhoeo 1
ieaxrpr
lseacnl ooi
os hna
aslsbeu=t vfarlisaebolers
il
ruelse
oaslegd
shuacs
htrauvee_bfeaelnser=epltaruced. by truth values “true” and “false”. A closed expression F can
be evaluated by the familiar rules of Boolean algebra, such as true ^ false = false or
true_false=true .
is a function q mapping variables (of F ) to truth values (i.e. true and false). This
Dmeafipnpintigonis2s0im.1il(aTrrtuoththaesstiogrnems wenetuasned teovaexlueacutitoenW).HIALEtr-uptrhogarsasmigsnwmhenertefoeracFh
ipsroagfruanmctvioanriaqblmeawpapsinmgavpapreiadbtloesa(obfinFary)toreter.uItfhwvaeluheasve(i.teru.tthruaessaingdnmfaelnset)q.Tfhoirs
ma bapopoilneagnisexspimreislsairontoFthethsetnorwesewcaenuaspepdlytotheexetcruthe aWsHsiIgLnEm-epnrtogtoratmhesewxphreersesieoanc,h
porbotagirnama cvloarsieadblfeorwmauslamaanpdptehdentoevaabluinataerythtirse.eF.oIrftwhies whaevbertireufltyhwasrsitiegnqm(Fen)t.q for
a boolean expression F then we can apply the truth assignment to the expression, Example 20.1. For instance, if q maps x to true, y and z to false, and F = (x^y)_¬z
obtain a closed formula and then evaluate this. For this we briefly write q (F ). then q (F ) = (true ^ false) _ ¬false which can be evaluated to true.
Example 20.1. For instance, if q maps x to true, y and z to false, and F = (x^y)_¬z Often boolean expressions are brought into normal forms:
then q (F ) = (true ^ false) _ ¬false which can be evaluated to true.
Definition 20.2 (conjunctive normal form (CNF)). A boolean expression is in
Often boolean expressions are brought into normal forms:
conjunctive normal form iff it is a finite conjunction of finite disjunctions of literals:
Definition 20.2 (conjunctive normal form (CNF)). A boolean expression is in (A A … A ) (A A … A )
p
r
e
s
s
i
o
n
s
11_12 _1n ^···^ m1_m2_ _mn 1m
conjunctive normal form iff it is a finite conjunction of finite disjunctions of literals: 4
where each Ai j is a literal, i.e. either a variable or a negated variable (x or ¬x). The (A11 _ A12 . . . _ A1n1 ) ^ · · · ^ (Am1 _ Am2 _ . . . _ Amnm )
disjunctive formulae (Ai1 _ Ai2 . . . _ Aini ) are called clauses.
where each Ai j is a literal, i.e. either a variable or a negated variable (x or ¬x). The
It is well known that any boolean expression can be brought into conjunctive normal disjunctive formulae (Ai1 Ai2 . . . Ain ) are called clauses.
THIS TIME
form (see Exercise 1).
__
i
Definition 20.1 (Truth assignment and evaluation). A truth assignment for F obtain a closed formula and then evaluate this. For this we briefly write q (F ).
20.1 A First NP-complete Problem
20.1 A First NP-complete Problem
is a function q mapping variables (of F ) to truth values (i.e. true and false). This mEaxpapminpgleis2s0i.m1.ilFarortointshteansctoer,eisf qwemuaspesdxttoetrxueec,uyteaWndHIzLtoEf-aplrsoeg,ranmdsFwh=er(ex^eayc)h_¬z
So far we have seen results about NP-complete problems, but as far as we know, ptrhoegnraqm(Fvar)ia=bl(etrwueas^mfaalpsep)ed_t¬ofalsbeinwarhyicthrecea.nIfbweevhalvueaterudthtoatsrsuieg.nment q for
So far we have seen results about NP-complete problems, but as far as we know,
there could still be no such NP-complete problem in the first place. Then we can a boolean expression F then we can apply the truth assignment to the expression,
therecouldstillbenosuchNP-completeprobleminthefirstplace.Thenwecanems
Often boolean expressions are brought into normal forms: obatpaipnlyacthloesepdrefvoiromuuslareasnudlttshetonethvaisluparteobthleism.Fionrtohridsewretobrpierflovyewtrhitaetqo(tFher).probl
apply the previous results to this problem in order to prove that other problems are NP-complete as well. Note that we have carried out a similar task in the C
are NP-complete as well. Note that we have carried out a similar task in the Com- Definition 20.2 (conjunctive normal form (CNF)). A boolean expression is
Example 20.1. For instance, if q m
aps x
ppuutatbaiblitlyitysescetciotino.nI.t IwtawsafisrsfitrshtoswhonwthnaththatetHhealtHinagltiPnrgobPlermobliesmunidsecuinddaebcleidanbdle
to tru
conjunctive normal form iff it is a finite conjunction of finite disjunctions of liter then q (F ) = (true ^ false) _ ¬false which can be evaluated to true.
CNF
ththenenrerdeudcutciotinonwawsaussuedsetdo tsohoswhotwhathoattheorthperrobplreombsleamresuanredeucnidaebcliedasblweealsl.well.
TThehefirfisrtsctocnocnrectretNePN-cPo-mcopmleptel
mewiellwenilcloeunnctoerunistearbiosuatbBouotleBaonoelxe-an
epteropb rloemblew
(A _A …_A )^···^(A _A _…_A ) Oftenbooleanex1p1ressi1o2nsareb1rnoughtintonomrm1alfomr2ms: mn
1m
pressions (or formulae). Recall that a Boolean expression, or formula, is made up of
pressions (or formulae). Recall that a Boolean expression, or formula, is made u
variables, binary conjunction operator ^ (“and”), disjunction operator _ (“or”) and Definition 20.2 (conjunctive normal form (CNF)). A boolean expression is in
variables, binary conjunction operator ^ (“and”), disjunction operator _ (“or”) where each Ai j is a literal, i.e. either a variable or a negated variable (x or ¬x).
unary negation operator ¬. An example is (x ^ y) _ ¬z.
conjunctive normal form iff it is a finite conjunction of finite disjunctions of literals:
unary negation operator ¬. An example is (x ^ y) _ ¬z. disjunctive formulae (Ai1 _ Ai2 . . . _ Aini ) are called clauses.
Recall that a boolean expression F is closed if it has no variables but variables Recall that a boolean expression F is closed if it has no variables but varia
hItavisewbeellnkrneopwl(aAncetdh_abtyAantryu.t.bh.o_voalAleuaens)e“^xtrp·ur·e·”s^sai(noAdn “cfa_anlAsbee”.b_Aro.cu.l.go_hsetAdinetoxp)croenssjuionnctFivecnaonr 11 12 1n m1 m2 mn
1m
have been replaced by truth values “true” and “false”. A closed expression F
be evaluated by the familiar rules of Boolean algebra, such as true ^ false = false or form (see Exercise 1).
be evaluated by the familiar rules of Boolean algebra, such as true ^ false = fals where each A is a literal, i.e. either a variable or a negated variable (x or ¬x). The
true _ false =i jtrue1 . 1 true_false=true .
disjunctive formulae (A _ A . . . _ A ) are called clauses.
Definition 20.3 (Satisi1fiabiil2ity). Ainboolean expression F is called satisfiable i
i
Definition 20.1 (Truth assignment and evaluation). A truth assignment for F evaluates to true for some truth assignment q .
Definition 20.1 (Truth assignment and evaluation). A truth assignment for It is well known that any boolean expression can be brought into conjunctive normal
is a function q mapping variables (of F ) to truth values (i.e. true and false). This
is a function q mapping variables (of F ) to truth values (i.e. true and false). form (see Exercise 1).
mapping is similar to the stores we used to execute WHILE-programs where each Example 20.2. An example for a Boolean expression in CNF is:
mapping is similar to the stores we used to execute WHILE-programs where e program variable was mapped to a binary tree. If we have truth assignment q for
Definition 20.3 (Satisfiability). A boolean expression F is called satisfiable if it program variable was mapped to a binary tree. If we have truth assignment q
e, y and z to false, and F = (x^y)_¬z
a boolean expression F then we can apply the truth assignment to the expression,
(p_¬q)^¬q^(¬p_ p_q) evaluates to true for some truth assignment q .
oabtbaionoalecalnosexdpfroersmsiuolna aFndththeenwevealcuaanteatphpisl.yFtohrethtriustwheasbsrigeflnymwenrittetoqt(hFe )e.xpress
is it satisfiable?
1oTbhtearienaarecslo-sceadllefdo“rtmruuthlataabnleds”thfoerneeacvhalBuoaotleeathniosp.eFraotrorththisatwfuellybreixepfllayinwitrsitsemqa(nFtic)s. Example 20.2. An example for a Boolean expression in CNF is:
Example 20.1. For instance, if q maps x to true, y and z to false, and F = (x^y)_¬z then q (F ) = (true ^ false) _ ¬false which can be evaluated to true.
Example 20.1. For instance, if q maps x to true, y and z to false, and F = (x ^ y) (p q) q ( p p q)
_¬ ^¬ ^ ¬ _ _
f it
F
This ach for ion,
_¬z
258
then q (F ) = (true ^ false) _ ¬false which can be evaluated to true.
Often boolean expressions are brought into normal forms:
1 There are so-called “truth tables” for each Boolean operator that fully explain its semantics.
conjunctive normal form iff it is a finite conjunction of finite disjunctions of literals: Definition 20.2 (conjunctive normal form (CNF)). A boolean expression is in
5
Often boolean expressions are brought into normal forms:
Definition 20.2 (conjunctive normal form (CNF)). A boolean expression is in
258
conjunctive normal form iff it is a finite conjunction of finite disjunctions of literals:
(A A … A )
(A A … A )
om- in and
als:
ex-
pof
and The
bles
mal
can eor
11_12 _1n1^···^m1_m2__mnm
(A _A …_A )^···^(A _A _…_A ) 11 12 1n m1 m2 mn
whereeachA isaliteral,i.e.eithera1variableoranegatedvariable(xmor¬x).The ij
disjunctive formulae (Ai1 _ Ai2 . . . _ Aini ) are called clauses.
where each Ai j is a literal, i.e. either a variable or a negated variable (x or ¬x).
Satisfiab
It is well known that any boolean expression can be brought into conjunctive normal disjunctive formulae (Ai1 _ Ai2 . . . _ Ain ) are called clauses.
i
form (see Exercise 1).
It is well known that any boolean expression can be brought into conjunctive nor
Definition 20.3 (Satisfiability). A boolean expression F is called satisfiable if it form (see Exercise 1).
evaluates to true for some truth assignment q .
Definition 20.3 (Satisfiability). A boolean expression F is called satisfiable
Example 20.2. An example for a Boolean expression in CNF is: evaluates to true for some truth assignment q .
(p_¬q)^¬q^(¬p_ p_q)
Example 20.2. An example for a Boolean expression in CNF is:
1 There are so-called “truth tables” for each Boolean operator that fully explain its semantics.
(p_¬q)^¬q^(¬p_ p_q)
1 There are so-called “truth tables” for each2B58oolean operator that fully explain its semantics.
ility
is it satisfiable?
258
6
The
mal
if it
CHAPTER 20. COMPLETE PROBLEMS 20.1. SAT
The example demonstrates that clauses can have different numbers of literals (here
CHAPTER 20. COMPLETE PROBLEMS 20.1. SAT
2, 1, and 3) and can consist of just one literal (clause 2). It also demonstrates that
a variable can appear positively and negatively in the same clause (here in clause 3 The example demonstrates that clauses can have different numbers of literals (here
we have p and ¬p).
2, 1, and 3) and can consist of just one literal (clause 2). It also demonstrates that
The SATisfiability Problem
The above expression in CNF is satisfiable. Simply choose q to be false. This a variable can appear positively and negatively in the same clause (here in clause 3
already makes the first and second clause true. The third clause is true whatever p we have p and ¬p).
and q are since ¬ p _ p is a tautology, meaning that it is true independently of the The above expression in CNF is satisfiable. Simply choose q to be false. This
value of p.
already makes the first and second clause true. The third clause is true whatever p
and q are since ¬p _ p is a tautology, meaning th2at it is true independently of the Definition 20.4 (SAT). The Satisfiability problem , short SAT, is defined as follows
value of p.
Definition 20.4 (SAT). The Satisfiability problem2, short SAT, is defined as follows
SAT = {F | F is a satisfiable boolean CNF expression } In other words, the SAT problem can be presented like this:
SAT = {F | F is a satisfiable boolean CNF expression }
• instance: a boolean expression F in CNF (conjunctive normal form)
In other words, the SAT problem can be presented like this: • question: is F satisfiable?
• instance: a boolean expression F in CNF (conjunctive normal form)
SAT is clearly decidable, as we can simply try all possible truth assignments for
• question: is F satisfiable?
F. Since there can only be finitely many variables in F we can test all truth as-
signments and return true if we found one that lets F evaluate to true. If F con- SAT is clearly decidable, as we can simply try all possible truth assignments for
tains n variable occurrences3 the size of the formula is O (n ⇥ log n) if we represent F. Since there can only be finitely many variables in F we ca2n test all truth as-
variable names in binary notation. In the worst case, there exist 2n possible truth signments and return true if we found one that lets F evaluate to true. If F con-
assignments to check (as for3each variable there are two choices: true and false). So tainsnvariableoccurrences thesizeoftheformulaisO(n⇥log2n)ifwerepresent
n
a brute-force search must take at least 2 ⇥O(n⇥log n) steps and thus SAT is in variable names in binary notation. In the worst case, 2there exist 2n possible truth
7
EXP.
assignments to check (as for each variable there are two choices: true and false). So
But we know more, thanks to a famous theorem by Cook (whom we have already a brute-force search must take at least 2n ⇥ O (n ⇥ log2 n) steps and thus SAT is in
encountered earlier) and Leonid Levin4: EXP.
But we know more, thanks to a famous theorem by Cook (whom we have already
Theorem 20.1 (Cook-Levin-Theorem4 [3, 14]). SAT is NP-complete. encountered earlier) and Leonid Levin :
Proof (Sketch). We need to show two facts:
Theorem 20.1 (Cook-Levin-Theorem [3, 14]). SAT is NP-complete.
1. thatSATAisTinNPand
Proof (Sketch). We need to show two facts:
1. tothiat.t
SA
in NiPsfiaanbdility
T is
problem
2. that it is a “hardest” problem for NP, i.e. all other NP problems
2. that it is a “hardest” problem for NP, i.e. all other NP problems Item 1 is easy. Let n be the number of different variable occurrenc
to it.
SAT is clearly decidable as one can try all possible truth
takes as certificate the right truth assignment q which is linear in th
assignments (there are only finitely many variables) but this
Item 1 is easy. Let n be the number of different variable occurrenc evaluation is then linear in the size of the formula (and thus polyno
leads to an exponential time algorithm.
takes as certificate the right truth assignment q which is linear in th item 2 we need to prove that any problem A 2 NP can be reduced
evaluation is then linear in the size of the formula (and thus polyno difficult as we don’t know what A is exactly. We therefore apply Th
item 2 we need to prove that any problem A 2 NP can be reduced to SAT. This is Stephen A. Cook
2difficereforeapplyThm.18.1which ThisSAT,whenSATisusedtodenotethe
proble 32
ult as we don’t know what A is exactly. We th version of the problem is also sometimes called CNF
TThehiSalAnT.,whenSATisusedtodenotethe 4 probl
Leonid Levin (born November 2, 1948) is a Soviet-American computer scientist who has ap-
3 The actual number of different variables is then less or equal n.
parently proved the same theorem as Stephen Cook independently behind the (then still existing)
4
“iroLneocunridtaiLne”v.in (born November 2, 1948) is a Soviet-American computer scientist who has ap-
parently proved the same theorem as Stephen Cook independently behind the (then still existing)
Proof sketch follows.
“iron curtain”.
259 259
can be reduced
can be reduced es. The verifier
e size of n and es. The verifier
mial). To show
e size of n and to SAT. This is
mial). To show m. 18.1 which
Cook-Levin Theorem:
m for unrestricted propositional formulae.
SAT is NP-complete. em for unrestricted propositional formulae.
ascvtueraslionnumofbethreopfrdoibfflermenitsvaalsrioabsolemseitsimthesnclaelslsedorCeNqFu
Leonid Levin
8
SAT is in NP Theorem: SAT is in NP.
Proof: We have to provide a polynomial time verifier for SAT:
Verifier takes a formula F and as certificate a truth assignment θ.
It checks whether F evaluates to true under the assignment θ (in time linear in number of variables of F and thus size of F).
Therefore the verifier runs in time polynomial in size of F.
9
SAT is NP-hard Theorem: SAT is NP-hard.
Proof Sketch: Given a decision problem x∈A we must find a polynomial time reduction f that maps x into a CNF F such that x∈A if and only if F is satisfiable.
We know A is in NP and thus (see Lecture 18) there is a nondet.TM program p that accepts A.
Idea: F describes all transition sequences of p with input x and ensure satisfiability of F iff there is an accepting sequence of p with input x.
Formula F can be constructed from p and x in time polynomial in x.
10
SAT is NP-complete Corollary: SAT is NP-complete.
Proof:
SAT is in NP-hard (previous slide).
SAT is in NP (two slides ago)
thus, by definition, SAT is NP-complete.
11
NP-complete problems
• The “hard” problems from Lecture 17: TSP, Graph Colouring, 0-1 Knapsack, Integer Linear Programming are all NP-complete (i.e. really “hard” in a precise sense).
• This can be shown by reducing SAT (or another NP-complete problem) in polynomial time to them.
12
because polynomial time reducibility is a transitive relation
More NP-complete Problems
• •
• •
• •
SAT = CNF-SAT
3-CNF-SAT is SAT where every clause has exactly 3 literals
http://www.cs.princeton.edu/~wayne/cs423/lectures/reductions-poly-4up.pdf
3-SAT ≤p DIR-HAM-CYCLE HAM-CYCLE ≤p TSP
why?
SAT ≤p 3-SAT (!)
(DIR-)HAM-CYCLE (Hamiltonian Cycle): given (directed) graph, is there a tour that visits each vertex exactly once.
13
Games
14
need to be generalised to arbitrary size
A chess board is 8 ⇥ 8 squares and similarly all other games have a certain fixed- popular in Japan and was discovered there by New Zealander Wayne Gould. . . . He
size board or game state. But it does not make sense to ask whether the “normal”
8 ⇥ 8 version of chess is NP-complete. For our considerations, we can only consider 15 able.
size board or game state. But it does not make sense to ask whether the “normal”
was able to get some puzzles printed in the London newspaper The Times beginning
8 ⇥ 8 version of chess is NP-complete. For our considerations, we can only consider in 2004. Soon after, Sudoku-fever swept England” [16] and the rest of the world in
games with arbitrary large descriptions, as we do asymptotic complexity after all, the following yesaor.the questions above only make sense for a generalised n ⇥ n board. Such a gen- eralisation is possible, but for games commonly known in their fixed-size version have
doku hTM
The standard version of Sudoku uses a 9 ⇥ 9 grid with 81 cells. The grid is di- like chess, it may result in a rather different kind of game, and playing it may
vided into nine 3 ⇥ 3 blocks (i.e. blocks of size 3). Some of the 81 cells are already
pretty much little in common with the original game.
containing numbers from 1 to 9. These filled-in cells are called givens. The goal
We will present the results for three types of games: Chess (Fig. 20.1), Su of the game is to fill in the remaining empty cells of the entire grid with digits
More NP-complete problems
(Fig. 20.2), and “match-three” based games like BejeweledTM or Candy Crus {1, 2, 3, 4, 5, 6, 7, 8, 9} suc1h4 that each row, each column, and each block contain each
(Fig. 20.3)
of the nine digits exactly once.
Again, one has to generalise the game, for which the block size comes in handy.
rank 3
4
5
6
1
2
5
gri
d,
su
bd
vi
de
di
to
n
he
n
m
be
rs3
us
ed
to
fil
di
4
it
a
ny
lo
ng
er.
A
fte
8
1
2
1
8
6
9
8 rmblkans
The block size is 3 (with 3 ⇥ 3 cells) in the standard version described above and
Theorem: ThoepSuodpokoupporopblem is
visualised in Fig 20.2.7One can now generalise the size, which is often also called
rank,from3ton.“ASudokuofranknisann⇥nsquarein NP-complete.6 0Z0Z0Z0Z 2 2 2
5 Z0Z0Z0Z0 blocks,eachofsizen⇥n.”[16].Inthisgeneralisedgametul
4 0Z0Z0Z0Z thecellsrangenowfro3m1ton2sotheymaynotbesinglegsr
Z0Z0Z0Z0
these generalisations we can now define a decision problem:
Definition 20.7 (Sudoku problem).
LETE PROBLEMS 20.3. PUZZLES AND GAMES
2 POPOPOPO 1 SNAQJBMR
abcdefgh
Fig. 20.1: Chess Board Fig. 20.2: Sudoku 2
• instance: a Sudoku board of rank n partially filled with numbers in {1, 2, . . . , n }.
• question: can one fill the blank cells with numbers in {1,2,…,n2}, such that each row, each column, and each of the n blocks contain each number exactly once?
So the Sudoku Problem as defined in Def. 20.7 is not actually about the solver (pro-
squares and similarly all other games have a certain fixed-
problem for the setter, namely whether the given starting position is actually solv-
ducing the solution would not give us a decision problem) but rather an important
CHAPTER 20. COMP
A chess board is 8⇥8
games with arbitrary large descriptions, as we do asymptotic complexity after all,
so the questions above only make sense for a generalised n ⇥ n board. Such a gen- eralisationispossible,butfTorhgaemoesrceommo2nl0y.k4no.wTnihnetheSirufidxeod-ksizuevPerrsionblem(asdefinedinDef.20.7)isNP-complete. like chess, it may result in a rather different kind of game, and playing it may have
pretty much little in common with the original game. Fig. 20.3: A typical “match-three” game screen
Proof. Asstrongerresultwasprovedin[29],namelythatSudokuisASN-complete, We will present the results for three types of games: Chess (Fig. 20.1), Sudoku
TM TM or Candy Crush
where ASN denotes the class of problems with a particular form of question: namely Games considered in this section
(Fig. 20.2), and “match-three” based games like Bejeweled
(Fig. 20.3)14
whether there are alternative solutions of the given problem with respect to certain
anals
ready given solutions. Since SAT can be easily shown to be ASP-complete, it
pop
45
“The match-3 puzzle game market is a cluttered space. . . . PopCap’s Bejew
follows that S
doku is al
Z0Z 0Z0
1
2
5
Z0Z
3
u
so NP-hard. It can be easily seen that Sudoku is in NP, sits at the top of the list alongside similar-looking titles that share similar na
6
Ca8nd1y2Crush Saga – a match-3 candy game, Candy Blast Mania – a match-3 c More NP-complete problems
as one can write a v
erifier that takes a solution candidate as certificate, and then
There’s Jewel World – a match-3 gem game, Jewel Mania – a match-3 gem g
22
verifies that this candidate is correct by checking for n columns, n rows, and n
0Z0
4
OPO
BMblRocks, whether each number in {1, . . . , n } occurs exactly once. This can clearly be
182 fgh469
ess Board
20.3: A typical “match-three” game screen
Games considered in this section
done in O n . 14 BejeweledTM is a trademark of PopCap Games and Candy CrushTM is a trademark of King
Fig. 20.2: Sudoku
Ltd.
e game market is a cluttered space. . . . PopCap’s Bejeweled st alongside similar-looking titles that share similar names. a match-3 gem game, Jewel Mania – a match-3 gem game, match-3 candy game, Candy Blast Mania – a match-3 candy
ark of PopCap Games and Candy CrushTM is a trademark of King.com 263
Theorem: 265
263
Deciding whether for a (generalised) Three-
Tile-Matching game, like Bejeweled or Candy
Crush, there is a sequence of moves such
that two specific tiles (gems, candies) can be swapped is NP-complete.
8 rmblk 7opopoeled
6 0Z0Z0
mes. andy .com
5 Z0Z0Z
40Z0Z0ame,
3 Z0Z0Z
2 POPOP
1 SNAQJ abcde
Fig. 20.1: Ch
Fig.
“The match-3 puzzl sits at the top of the li There’s Jewel World – Candy Crush Saga – a
14 BejeweledTM is a tradem Ltd.
16
20.3.1 Chess
CHAPTER 20. COMPLETE PROBLEMS 20.3. PUZZLES
Theorem 20.3 ([5]). The Chess Problem (as defined in Def. 20.6) is EXP-complete.
20.4. DATABASE QUERIES CHAPTER 20. COMPLETE PROBLEMS
Proof.Oneusespolynomialtimereductionoftheproblem“TGhe3m(aatcsh-d3epufiznzledgaminem[2ar0ke]t)isaclutteredspace….PopC
sits at the top of the list alongside similar-looking titles that share Definition20.8.ArelTahtieornea’slJdeawtaelbaWsoerlcdon–saismtsaotcfha-3figneimtegsaetmDe,,JtehweedloMmaanina(–foarmatc simplification there isCjuasntdoyneCdruosmhaSiang,abu–taitmcoautclhd-e3acsailnydeyngcaomde,gCeannedrayllBylasllt Mtypaensia – a
e rank (or degree) of
and Candy CrushTM is a trade njunctive queries on
3
e (D,R1,…,Rs) is a on of relations. More
that are of the form er a variable yj (j 2
s SQL query. Let us
h a maximum length RDER relation O, the write, for instance, a ccount number A123
me’)
he last two. This can
to Chess. More details can be found in [5].
A chess board is 8 ⇥ 8 squares and similarly all other games have size board or game state. But it does not make sense to ask whethe our considerations, we ca as we do asymptotic comp or a generalised n ⇥ n boar
mmonly known in their fix nt kind of game, and playi
ginal game.
pes of games: Chess (Fig.
mes like BejeweledTM or C 45
12
3 4
812 18 6
Fig. 20.2: Sudo
8 ⇥ 8 version of chess is NP-complete. For Chess is a popular two-player strategy board game which is probably 1,500 years
games with arbitrary large descriptions, old and originated in Asia. It became very popular in the 19th century across the
eralisation is possible, but for games co world and it was in the second half of that century when tournaments started. The
like chess, it may result in a rather differe rules are relatively complicated, so we will not repeat them here (they can be found
An EXP-complete game
(Fig. 20.2), and “match-three” based ga
e.g. in [26])15.
pretty much little in common with the ori We will present the results for three ty
First, the game has to be generalised to arbitrary size for our14purposes which is
explained in [5]:
(Fig. 20.3)
“We let generalized chess be any game of a class of chess-type-games with
Theorem:
8 rmblkans
one king per side played on an n ⇥ n chessboard. The pieces of every game in the
The (generalised) Chess problem is
7
class are subject to the same movement rules as in 8 ⇥ 8 ches Z0Z0Z0Z0
WhEiteXaPnd-cBolamckplaewtnes.,rooks,bishopsandqueenseachincr0eaZse0sZas0sZom0eZfrac- how generalise chess to 3 Z0Z0Z0Z0
tional power of n. Beyond this growth condition, the initial position is immaterial,
Definition 20.6 (Chess problem).
Fig. 20.1: Chess Board
a n x n board??? 2 POPOPOPO
since we analyze the problem of winning for an arbitrary boardSpNosAitiQonJ.”BMR abcdefgh
• instance: an arbitrary position of a generalized chess-game on an n ⇥ n chess- board
• question: can White (or Black) win from that position?
The number of possible configurations in n ⇥ n chess is obviously bounded by 13n2
as there are six different pieces for each player (and the can be no piece on a square).
Therefore17, The Chess Problem is in EXP. But one can show more about this Fig. 20.3: A typical “ma
so the questions above only make sense f
8×8 chess 16
opopopop
6 0Z0Z0Z0Z
s, and the number of
5
4
1
version of chess:
tch-three” game screen Games considered in this section
17
15
N
boolean database query expression
oblem
It is worth remembering what this means for classic chess: “Thus, while we may
in use) and finitely many relations Ri ✓ Dri where ri is called th
havesaidverylittleifanythingabout8⇥8chess,i wehave,infact,saidasmuch Ltd.
on
-c
he
ss p
lay
ers
are
encou
rag
ed t
50 moves then it’s a draw. relations
ol
ook t
hem
up
an
14 TM therelationRand1iBejesw.eled isatrademarkofPopCapGames
aboutthecomplexityofdecidingwinningpoWsietifolnloswi[n1]c,hthesfisrsatspatpheerotnoothlessoubfjercetd,tuocdteifioneco relational databases:
and completeness in computational complexity allow us to say.” [5] 26 D Definition 20.9. A conjunctive query for a relational databas
a
t
a
b
a
s
e
Q
u
e
r
y
E
v
CHAPTER20.COMPLETEPROBLEMSthataskswheth2e0r.t4he.reDexAistTyA.B..,AySthEatQfulUfilEaRcoInEjuSncti 16 1n
without the 50 move rule that says that if no pawn was moved and no piece captured in the last precisely, they are of the form
•• iqnusteasnticoen::gdivoens fa reevlaltuioantealtodatrtaubeaisned2(aD6t4a,bRas,e..(.D,R,R) a,.n.d.,aRb)o?olean conjunctive 1s1s
Note that every such conjunctive query can be expressed a query f look at an example.
Theorem 20.6 ([1]). The Query Evaluation problem is NP-complete when applying • question: does f evaluate to true in dataEbxamspele(2D0.,3R. As,s.u.m.e, wRe )h?ave the following three schemas
1s
the combined complexity measure, i.e. measure time usage w.r.t. database and query
ORDER(oid,account) Texhperoersesmion20s.i6ze(.[1]). The Query Evaluation pPrRoObDlUeCmT(ipsiNd,Ps-eclolmerp)lete when applying
the combined complexity measure, i.e. measure time usage w.r.t. database and query
Assume further (for simplicity) the domain D are strings (wit This well-known result was first proved in a seminal paper by Chandra and Merlin
expression size.
in 1977. “However, the main factor responsible for the high complexity of the prob-
a
l
u
d
pla
a
y
thi
t
INFO(oid,pid,quantity)
of some sort) and, for reason of brevity, let us abbreviate the O Polynomial for all queries PoRlOyDnUCoTmreilatlionfoPransdot-hecaINllFeOdrelatcioyncIl.iWce can now
i
o
s
clas
n
P
sic ga
me
r
.
CD17HeAfinPiTtiEoRn20.1C0O(QMuPeLryETEEvaPlRuOatBioLnEpMrSoblem). 20.4. DAT9AyB..A.9SyE.aQ^U..E.^RaIES 1n1m
Of course, not all these positions are legal positions but this can be ignored for this approxima-
tion.
• instance: given a relational database (D,R1,…,Rs) and a booleain conjunctive
where 9 stands for “there exists”, the a are atomic formulae Definition20.10(QueryEvaluationprobRlej(mt1,.)..,t)where1jsandeacht (1lk)iseith
query f D is (finite) domain of schema columns {1,…,n}) or a constant.
kl
This well-known result was first proved in a seminal paper by Chandra and Merlin lemisthelengthoftheinputformulaancdonjnunoctivtehqeuesriyztehaotcfhethckeswdhaethaebrathseere.isTahnisordeorfeosra
in size of data alone (data queries, where joins can be done
in1977.“However,themainfactorresponsthiabtliencfluodresthaeprohdiugchtincqoumanptiltyexofit1y00otfhatthiesspolrdobby-Acme. not fit the practical situation very well, because usually one evaluates a short query
complexity) without holding “intermediate results”
lem is the length of the input formula and not the size of the database. This does against a large database.” [8]. One way to try to remedy this issue is “parametrised
9x,p. O(x,‘A123’})^I(x,p,100)^P(p,‘Ac not fit the practical situation very well, because usually one evaluates a short query
complexity” (see [4]). But this does not really lead to (parameterised) tractability The variable x “relates” the first two relations and variable p t
against a large database.” [8]. One way to try to remedy this issue is “parametrised either (see [18]) and a detailed exposition is beyond the scope of this book. How-
simplification uses a notion of “acyclicity” defined next.
ever, [28] was the first to show that simplifying the conjunctive queries helps. The
sDimefiplnifiitcioatnio2n0u.1s1es(ajoninottioreneo).f L“aectyQclbiceitay”Bdoeofilenaend qnuexert.y
P.seller = ’Acme’
18
be expressed as SQL query in the following way:
complexity” (see [4]). But this does not really lead to (parameterised) tractability ever, [28] was the first to show that simplifying the conjunctive queries helps. The
either (see [18]) and a detailed exposition is beyond the scope of this book. How-
SELECT DISTINCT 1
FROM INFO I JOIN ORDER O ON O.oid = I.oid
JOIN PRODUCT P ON P.pid = I.pid
WHERE O.account = ’A123’ AND
A
a r n l
e n
a
a s h
m
m
END
© 2008-21. Bernhard Reus, University of Sussex
Next time:
How do wNexdteatilmwei:th NP- complete prob?lems then if they are so hard?
19