Université Paris Cité

LIPADE

Algorithmic Complexity
Non-Deterministic Time

Jean-Guy Mailly (jean-guy.mailly@u-paris.fr)

2023
 Outline
1

Non-Deterministic Time Complexity Classes

Polynomial Hierarchy

Complexity of Well-Known Problems

SAT and Related Problems
Other Theoretical Problems
Video Games

Determining the Complexity of a Problem

J.-G. Mailly | Non-Deterministic Time

 Reminder on DTM vs NDTM [Turing 1936]
2

Deterministic Non-Deterministic
(q0 , x0 ) (q0 , x0 )
δ δ
δ δ
(q1 , x1 ) ... (qk , xk )
(q1 , x1 ) δ
δ δ δ
...
... ...
...
δ δ
δ δ
δ
(qm , xm ) (qn , xn )
(qn , xn ) (qo , xo ) (qp , xp )

J.-G. Mailly | Non-Deterministic Time

 Intuition on Solving an Exponential Problem...
3

. . . ... with DTM

I Linear calculations since δ is a 1 to 1 mapping from
configurations to transitions
I Exponential number of steps cannot be avoided

J.-G. Mailly | Non-Deterministic Time

 Intuition on Solving an Exponential Problem...
3

. . . ... with DTM

I Linear calculations since δ is a 1 to 1 mapping from
configurations to transitions
I Exponential number of steps cannot be avoided

. . . ... with NDTM

I The tree structure can simulate parallel computing
I The solving time is the length of the longest branch of the tree
I COULD BE polynomial (no guarantee in general)
I When it stays exponential, it COULD BE smaller exponential
(e.g. O(2n ) steps instead of O(10n ))

J.-G. Mailly | Non-Deterministic Time

 Really Naive Example
4

Solving an Equation...
Does f (n) = 0 have a solution, with n ∈ [0, 1, . . . , 109 ]?

J.-G. Mailly | Non-Deterministic Time

 Really Naive Example
4

Solving an Equation...
Does f (n) = 0 have a solution, with n ∈ [0, 1, . . . , 109 ]?

. . . ... with DTM

I Compute f (0). If it works, fine, otherwise compute f (1), then
f (2),. . .

J.-G. Mailly | Non-Deterministic Time

 Really Naive Example
4

Solving an Equation...
Does f (n) = 0 have a solution, with n ∈ [0, 1, . . . , 109 ]?

. . . ... with DTM

I Compute f (0). If it works, fine, otherwise compute f (1), then
f (2),. . .
I Not efficient: if the solutions of the equation are huge (e.g. 109 ),
then a lot of useless calculations are made

J.-G. Mailly | Non-Deterministic Time

 Really Naive Example
4

Solving an Equation...
Does f (n) = 0 have a solution, with n ∈ [0, 1, . . . , 109 ]?

. . . ... with DTM

I Compute f (0). If it works, fine, otherwise compute f (1), then
f (2),. . .
I Not efficient: if the solutions of the equation are huge (e.g. 109 ),
then a lot of useless calculations are made

. . . ... with NDTM

I Compute f (i) on the i th branch of the tree, with 0 ≤ i ≤ 109

J.-G. Mailly | Non-Deterministic Time

 Really Naive Example
4

Solving an Equation...
Does f (n) = 0 have a solution, with n ∈ [0, 1, . . . , 109 ]?

. . . ... with DTM

I Compute f (0). If it works, fine, otherwise compute f (1), then
f (2),. . .
I Not efficient: if the solutions of the equation are huge (e.g. 109 ),
then a lot of useless calculations are made

. . . ... with NDTM

I Compute f (i) on the i th branch of the tree, with 0 ≤ i ≤ 109
I Whatever the solution of the problem, it is obtained in the time of a
« single » f (i) computation

J.-G. Mailly | Non-Deterministic Time

 Non-Deterministic Complexity Classes
5

Evaluating Time with NDTM

Given a function f : N 7→ N, NTIME(f (n)) is the set of all languages
decided by a NDTM M in less than g(n) steps (longer branch), with
g(n) ∈ O(f (n))

J.-G. Mailly | Non-Deterministic Time

 Non-Deterministic Complexity Classes
5

Evaluating Time with NDTM

Given a function f : N 7→ N, NTIME(f (n)) is the set of all languages
decided by a NDTM M in less than g(n) steps (longer branch), with
g(n) ∈ O(f (n))

Proposition
I ∀f : N 7→ N, then DTIME(f (n)) ⊆ NTIME(f (n))
I ∀f (n) ≥ n, NTIME(f (n)) is closed for finite union and finite
intersection
I if L1 , . . . , Lm ∈ NTIME(f (n)), then L1 ∪ · · · ∪ Lm ∈ NTIME(f (n))
I if L1 , . . . , Lm ∈ NTIME(f (n)), then L1 ∩ · · · ∩ Lm ∈ NTIME(f (n))

J.-G. Mailly | Non-Deterministic Time

 Non-Deterministic Complexity Classes
5

Evaluating Time with NDTM

Given a function f : N 7→ N, NTIME(f (n)) is the set of all languages
decided by a NDTM M in less than g(n) steps (longer branch), with
g(n) ∈ O(f (n))

Proposition
I ∀f : N 7→ N, then DTIME(f (n)) ⊆ NTIME(f (n))
I ∀f (n) ≥ n, NTIME(f (n)) is closed for finite union and finite
intersection
I if L1 , . . . , Lm ∈ NTIME(f (n)), then L1 ∪ · · · ∪ Lm ∈ NTIME(f (n))
I if L1 , . . . , Lm ∈ NTIME(f (n)), then L1 ∩ · · · ∩ Lm ∈ NTIME(f (n))

Closeness under complement is an open question. The answer is

mainly assumed to be « no »

J.-G. Mailly | Non-Deterministic Time

 Polynomial vs Exponential Time
6

Definition
I The complexity class NP is the set of languages decided in
polynomial time by a NDTM, i.e
[
NP = NTIME(nk )
k ∈N

I The complexity class NEXP is the set of languages decided in

exponential time by a NDTM, i.e
[ k
NEXP = NTIME(2n )
k ∈N

J.-G. Mailly | Non-Deterministic Time

 Polynomial vs Exponential Time
6

Definition
I The complexity class NP is the set of languages decided in
polynomial time by a NDTM, i.e
[
NP = NTIME(nk )
k ∈N

I The complexity class NEXP is the set of languages decided in

exponential time by a NDTM, i.e
[ k
NEXP = NTIME(2n )
k ∈N

Theorem P ⊆ NP ⊆ EXP ⊆ NEXP

Moreover, P 6= EXP, NP 6= NEXP.
P = NP, NP = EXP or EXP = NEXP are open questions

J.-G. Mailly | Non-Deterministic Time

 Polynomial vs Exponential Time
6

Definition
I The complexity class NP is the set of languages decided in
polynomial time by a NDTM, i.e
[
NP = NTIME(nk )
k ∈N

I The complexity class NEXP is the set of languages decided in

exponential time by a NDTM, i.e
[ k
NEXP = NTIME(2n )
k ∈N

Theorem P ⊆ NP ⊆ EXP ⊆ NEXP

Moreover, P 6= EXP, NP 6= NEXP.
P = NP, NP = EXP or EXP = NEXP are open questions: Millennium
Prize Problems
J.-G. Mailly | Non-Deterministic Time
 Examples of Problems in NP
7

Clique
I Input: G a graph, k ∈ N
I Problem: Does G contain a clique with size k ?

Subset Sum
I Input: {a1 , . . . , an } ⊂ N, k ∈ N
I Problem: Is there a subset S ⊆ {a1 , . . . , an } s.t. x∈S x = k ?
P

J.-G. Mailly | Non-Deterministic Time

 Outline
8

Non-Deterministic Time Complexity Classes

Polynomial Hierarchy

Complexity of Well-Known Problems

SAT and Related Problems
Other Theoretical Problems
Video Games

Determining the Complexity of a Problem

J.-G. Mailly | Non-Deterministic Time

 Complement of a Class
9

Definition
Given a complexity class C, its complement COC is defined by

CO C = {P̄ | P ∈ C}

For complexity classes C defined with DTM, COC = C

J.-G. Mailly | Non-Deterministic Time

 Complement of a Class
9

Definition
Given a complexity class C, its complement COC is defined by

CO C = {P̄ | P ∈ C}

For complexity classes C defined with DTM, COC = C

Important Complement Class

CO NP is the complement complexity class of NP

J.-G. Mailly | Non-Deterministic Time

 Examples of Problems in CONP
10

No Clique
I Input: G a graph, k ∈ N
I Problem: Does G contain no clique with size k ?

Why determining if a graph has a k -clique has not the same

complexity than proving that it has no k -clique?

J.-G. Mailly | Non-Deterministic Time

 Examples of Problems in CONP
10

No Clique
I Input: G a graph, k ∈ N
I Problem: Does G contain no clique with size k ?

Why determining if a graph has a k -clique has not the same

complexity than proving that it has no k -clique?
I To accept an instance of Clique: just exhibit one example of a
k -clique to answer YES
I To accept an instance of No Clique: you have to check every
k -subgraph G0 and check if it’s a clique

J.-G. Mailly | Non-Deterministic Time

 Relations between P, NP, CONP
11

Theorem
P ⊆ NP and P ⊆ CONP
but NP = CONP or NP 6= CONP is still an open question

J.-G. Mailly | Non-Deterministic Time

 Relations between P, NP, CONP
11

Theorem
P ⊆ NP and P ⊆ CONP
but NP = CONP or NP 6= CONP is still an open question

Idea of the polynomial hierarchy: define generalized complexity

classes with similar inclusion pattern

J.-G. Mailly | Non-Deterministic Time

 Oracle Machines
12

Definition
Given C1 , C2 two complexity classes, CC
1 is the set of all problems
2

which can be solved by a Turing machine from the class C1 with an

oracle from the class C2

J.-G. Mailly | Non-Deterministic Time

 Oracle Machines
12

Definition
Given C1 , C2 two complexity classes, CC
1 is the set of all problems
2

which can be solved by a Turing machine from the class C1 with an

oracle from the class C2

Oracle of class C2 : abstract entity which can solve in one step a

problem from C2

J.-G. Mailly | Non-Deterministic Time

 Oracle Machines
12

Definition
Given C1 , C2 two complexity classes, CC
1 is the set of all problems
2

which can be solved by a Turing machine from the class C1 with an

oracle from the class C2

Oracle of class C2 : abstract entity which can solve in one step a

problem from C2

Example
A problem belongs to PNP if it can be solved by a DTM with
polynomially many calls to a NP oracle (i.e. a polynomial NDTM)

J.-G. Mailly | Non-Deterministic Time

 Polynomial Hierarchy
[Stockmeyer 1976]
13

Definition
The polynomial hierarchy is the set of complexity classes defined
recursively by
P
I ∆P0 = ΣP0 = ΠP0 = P I ΣPk +1 = NPΣk
P P
I ∆Pk +1 = PΣk I ΠPk +1 = CONPΣk

J.-G. Mailly | Non-Deterministic Time

 Polynomial Hierarchy
[Stockmeyer 1976]
13

Definition
The polynomial hierarchy is the set of complexity classes defined
recursively by
P
I ∆P0 = ΣP0 = ΠP0 = P I ΣPk +1 = NPΣk
P P
I ∆Pk +1 = PΣk I ΠPk +1 = CONPΣk

J.-G. Mailly | Non-Deterministic Time

 Polynomial Hierarchy
[Stockmeyer 1976]
13

Definition
The polynomial hierarchy is the set of complexity classes defined
recursively by
P
I ∆P0 = ΣP0 = ΠP0 = P I ΣPk +1 = NPΣk
P P
I ∆Pk +1 = PΣk I ΠPk +1 = CONPΣk

CO NP

NP

J.-G. Mailly | Non-Deterministic Time

 Polynomial Hierarchy
[Stockmeyer 1976]
13

Definition
The polynomial hierarchy is the set of complexity classes defined
recursively by
P
I ∆P0 = ΣP0 = ΠP0 = P I ΣPk +1 = NPΣk
P P
I ∆Pk +1 = PΣk I ΠPk +1 = CONPΣk

CO NP

P ∆P2

NP

J.-G. Mailly | Non-Deterministic Time

 Polynomial Hierarchy
[Stockmeyer 1976]
13

Definition
The polynomial hierarchy is the set of complexity classes defined
recursively by
P
I ∆P0 = ΣP0 = ΠP0 = P I ΣPk +1 = NPΣk
P P
I ∆Pk +1 = PΣk I ΠPk +1 = CONPΣk

CO NP ΠP2

P ∆P2

NP ΣP2

J.-G. Mailly | Non-Deterministic Time

 Polynomial Hierarchy
[Stockmeyer 1976]
13

Definition
The polynomial hierarchy is the set of complexity classes defined
recursively by
P
I ∆P0 = ΣP0 = ΠP0 = P I ΣPk +1 = NPΣk
P P
I ∆Pk +1 = PΣk I ΠPk +1 = CONPΣk

CO NP ΠP2

P ∆P2 ∆P3

NP ΣP2

J.-G. Mailly | Non-Deterministic Time

 Polynomial Hierarchy
[Stockmeyer 1976]
13

Definition
The polynomial hierarchy is the set of complexity classes defined
recursively by
P
I ∆P0 = ΣP0 = ΠP0 = P I ΣPk +1 = NPΣk
P P
I ∆Pk +1 = PΣk I ΠPk +1 = CONPΣk

CO NP ΠP2 ΠP3

P ∆P2 ∆P3 ...

NP ΣP2 ΣP3

J.-G. Mailly | Non-Deterministic Time

 Polynomial Hierarchy
[Stockmeyer 1976]
13

Definition
The polynomial hierarchy is the set of complexity classes defined
recursively by
P
I ∆P0 = ΣP0 = ΠP0 = P I ΣPk +1 = NPΣk
P P
I ∆Pk +1 = PΣk I ΠPk +1 = CONPΣk

CO NP ΠP2 ΠP3

P ∆P2 ∆P3 ...

NP ΣP2 ΣP3

I C1 → C2 means that C1 ⊆ C2
I PH = i∈N ΣPi
S

J.-G. Mailly | Non-Deterministic Time

 Relative Hardness of Problems
14

Polynomial-Time Functional Reduction

A polynomial-time functional reduction f is a total computable function
from a problem P1 to a problem P2 such that, for any instance i of P1 ,
I f (i) can be computed in polynomial-time in the size of i
I i is a positive instance of P1 iff f (i) is a positive instance of P2
Notation:
P1 ≤Pf P2

J.-G. Mailly | Non-Deterministic Time

 Relative Hardness of Problems
14

Polynomial-Time Functional Reduction

A polynomial-time functional reduction f is a total computable function
from a problem P1 to a problem P2 such that, for any instance i of P1 ,
I f (i) can be computed in polynomial-time in the size of i
I i is a positive instance of P1 iff f (i) is a positive instance of P2
Notation:
P1 ≤Pf P2

C-hardness
A problem P is C-hard iff for each P 0 ∈ C, P 0 ≤Pf P

Intuition: P is at least as hard to solve as every problem from C

J.-G. Mailly | Non-Deterministic Time

 Completeness
15

C-completeness
A problem P is C-complete iff it is C-hard and P ∈ C

Intuition: P is one of the hardest problems from C

J.-G. Mailly | Non-Deterministic Time

 Completeness
15

C-completeness
A problem P is C-complete iff it is C-hard and P ∈ C

Intuition: P is one of the hardest problems from C

A lot of interesting AI problems are complete for NP, CONP, ΣP2 or ΠP2

J.-G. Mailly | Non-Deterministic Time

 Outline
16

Non-Deterministic Time Complexity Classes

Polynomial Hierarchy

Complexity of Well-Known Problems

SAT and Related Problems
Other Theoretical Problems
Video Games

Determining the Complexity of a Problem

J.-G. Mailly | Non-Deterministic Time

 SAT
Syntax and Semantics of Propositional Logic
17

I V = {x1 , . . . , xn } a set of Boolean variables

I C = {¬, ∨, ∧} a set of connectives
I A well formed formula (wff) φ is:
I an atom: φ = xi
I the negation of a wff: φ = ¬ψ
I the conjunction of two wffs: φ = ψ1 ∧ ψ2
I the disjunction of two wffs: φ = ψ1 ∨ ψ2
I Interpretation ω : V 7→ B = {0, 1}
I Semantics of connectives:
I ω(¬ψ) = 1 − ω(ψ)
I ω(ψ1 ∧ ψ2 ) = min(ω(ψ1 ), ω(ψ2 ))
I ω(ψ1 ∨ ψ2 ) = max(ω(ψ1 ), ω(ψ2 ))
I ω |= φ iff ω(φ) = 1

J.-G. Mailly | Non-Deterministic Time

 SAT
Complexity
18

Theorem [Cook 1971]

Given a propositional formula φ, the SAT problem consists in
determining whether φ is consistent, i.e. whether φ has a model.
SAT is NP-complete.

General knowledge: SAT is the first problem which has been proved
NP-complete.

J.-G. Mailly | Non-Deterministic Time

 SAT
Complexity
18

Theorem [Cook 1971]

Given a propositional formula φ, the SAT problem consists in
determining whether φ is consistent, i.e. whether φ has a model.
SAT is NP-complete.

General knowledge: SAT is the first problem which has been proved
NP-complete.
The power of propositional logic to express a lot of « real » problems
(solving games, planning,. . . ) has led to the development of quite
efficient methods to solve NP-complete problems. But even these
methods do not allow to solve ALL instances of NP-complete
problems.

J.-G. Mailly | Non-Deterministic Time

 Normal Forms
19

I A literal l is either a variable x or its negation ¬x

I A clause is a disjunction of literals l1 ∨ · · · ∨ ln
I A cube is a conjunction of literals l1 ∧ · · · ∧ ln

Conjunctive Normal Form

A formula is in CNF if it is a conjunction of clauses

Disjunctive Normal Form

A formula is in DNF if it is a disjunction of cubes

J.-G. Mailly | Non-Deterministic Time

 Complexity of SAT with Normal Forms
20

CNF-SAT
Any formula can be transformed in an equivalent CNF formula
I The transformation can be done in polynomial time

J.-G. Mailly | Non-Deterministic Time

 Complexity of SAT with Normal Forms
20

CNF-SAT
Any formula can be transformed in an equivalent CNF formula
I The transformation can be done in polynomial time
I Solving CNF-SAT is NP-complete

J.-G. Mailly | Non-Deterministic Time

 Complexity of SAT with Normal Forms
20

CNF-SAT
Any formula can be transformed in an equivalent CNF formula
I The transformation can be done in polynomial time
I Solving CNF-SAT is NP-complete

DNF-SAT
Any formula can be transformed in an equivalent DNF formula
I Solving DNF-SAT is polynomial

J.-G. Mailly | Non-Deterministic Time

 Complexity of SAT with Normal Forms
20

CNF-SAT
Any formula can be transformed in an equivalent CNF formula
I The transformation can be done in polynomial time
I Solving CNF-SAT is NP-complete

DNF-SAT
Any formula can be transformed in an equivalent DNF formula
I Solving DNF-SAT is polynomial
I The transformation cannot be done in polynomial time :(

J.-G. Mailly | Non-Deterministic Time

 Tractable Classes
2SAT 21

I A binary clause is a clause with two literals: l1 ∨ l2

I A 2CNF is a CNF formula with only binary clauses

Complexity of 2SAT
Determining if a 2CNF formula is satisfiable is in P

J.-G. Mailly | Non-Deterministic Time

 Tractable Classes
Horn-SAT 22

I A Horn clause is a clause with at most one positive literal:

x1 ∨ ¬x2 · · · ∨ ¬xn
I A Horn formula (or Horn CNF) is a CNF formula with only Horn
clauses

Complexity of Horn-SAT
Determining if a Horn formula is satisfiable is in P

J.-G. Mailly | Non-Deterministic Time

 Quantified Boolean Formula
23

I A canonical QBF is a formula Q1 X1 , Q2 X2 , . . . Qn Xn , φ with

I Qi ∈ {∀, ∃} and Qi 6= Qi+1
I X1 , . . . Xn form a partition of the Boolean variables in φ
I φ is a propositional formula
I E.g. ∃x1 , x3 , ∀x2 , (¬x1 ∨ x2 ) ∧ (¬x3 ∨ x2 )
I ∃n QBF is the decision problem: is the QBF ∃X1 , ∀X2 , . . . Qn Xn , φ
true?
I ∀n QBF is the decision problem: is the QBF ∀X1 , ∃X2 , . . . Qn Xn , φ
true?

Complexity of ∃n QBF Complexity of ∀n QBF

∃n QBF is ΣPn -complete ∀n QBF is ΠPn -complete

J.-G. Mailly | Non-Deterministic Time

 Set Packing
24

Definition
Given a universe U and S ⊆ 2U , a set packing of U is a subset C ⊆ S
s.t. all elements in C are pairwise disjoints

Theorem [Karp 1972]

Given U, S and k ∈ N, determining whether there is a set packing C
s.t. |C| = k is NP-complete

J.-G. Mailly | Non-Deterministic Time

 Knapsack Problem
25

Definition
Given a list of objects x1 , . . . , xn , each of them associated with a value
v1 , . . . , vn and a weight w1 , . . . , wn , a knapsack with a maximal weight
W , and an integer V , is it possible to fill the bag with some of the
objects, such that the sum of the weights is lesser than W and the
sum of the values is greater than V ?

Theorem
Solving the Knapsack Problem is NP-complete

J.-G. Mailly | Non-Deterministic Time

 Kernel of a Graph
26

Definition
A graph is a pair G = hN, Ei where elements of N are called nodes
and E ⊆ N × N is the set of edges between the nodes. A kernel of G
is a subset K ⊆ N s.t. ∀ni , nj ∈ K , (ni , nj ) ∈
/ E and ∀nj ∈ N \ K ,
∃ni ∈ K s.t. (ni , nj ) ∈ E

Theorem [Creignou 1995]

Given a graph G, determining whether G has a kernel is
NP-complete.

J.-G. Mailly | Non-Deterministic Time

 Shortest Implicant
27

Definition
An implicant of a formula φ is a conjunction of literals c = x1 ∧ · · · ∧ xn
s.t. c ` φ.

Theorem [Umans 2001]

Given a formula φ and k ∈ N, determining whether φ has an implicant
c s.t. |c| ≤ k is ΣP2 -complete

J.-G. Mailly | Non-Deterministic Time

 Super Mario Bros.
28

Theorem [Aloupis et al. 2015]

It is NP-hard to decide whether the goal is reachable from the start of
a stage in generalized Super Mario Bros.
J.-G. Mailly | Non-Deterministic Time
 Donkey Kong Country
29

Theorem [Aloupis et al. 2015]

It is NP-hard to decide whether the goal is reachable from the start of
a stage in generalized Donkey Kong Country.
J.-G. Mailly | Non-Deterministic Time
 The Legend of Zelda
30

Theorem [Aloupis et al. 2015]

It is NP-hard to decide whether a given target location is reachable
from a given start location in generalized Legend of Zelda, LoZ II: The
Adventure of Link and LoZ: A Link to the Past.
J.-G. Mailly | Non-Deterministic Time
 Metroid
31

Theorem [Aloupis et al. 2015]

It is NP-hard to decide whether a given target location is reachable
from a given start location in generalized Metroid.
J.-G. Mailly | Non-Deterministic Time
 Pokémon
32

Theorem [Aloupis et al. 2015]

I It is NP-hard to decide whether a given target location is
reachable from a given start location in generalized Pokémon.
I It is NP-complete to decide whether a given target location is
reachable from a given start location in generalized Pokémon in
which the only overworld game elements are enemy Trainers.
J.-G. Mailly | Non-Deterministic Time
 2048 and Variants
33

Theorem [Langerman and Uno 2018]

In 2048 (and several variants), it is NP-hard to decide whether a given
starting position can be played to reach a specific (constant) tile value
J.-G. Mailly | Non-Deterministic Time
 More Information on Complexity of Problems
34

I [Garey and Johnson 1979]: One of the most well-known book on

the topic, a lot of classical results
I [Schaefer and Umans 2002a, Schaefer and Umans 2002b]:
More recent collection of results

J.-G. Mailly | Non-Deterministic Time

 Outline
35

Non-Deterministic Time Complexity Classes

Polynomial Hierarchy

Complexity of Well-Known Problems

SAT and Related Problems
Other Theoretical Problems
Video Games

Determining the Complexity of a Problem

J.-G. Mailly | Non-Deterministic Time

 Bounds of Complexity
36

In some cases, it’s not easy to determine precisely the complexity of

a problem, but we can give lower/upper bounds.
I Lower bound: C-hardness. E.g. if P is NP-hard, P is at least as
hard as SAT
I Upper bound: C membership. E.g. if P ∈ ΣP2 , P is at most as
hard as Shortest Implicant problem.

J.-G. Mailly | Non-Deterministic Time

 Bounds of Complexity
36

In some cases, it’s not easy to determine precisely the complexity of

a problem, but we can give lower/upper bounds.
I Lower bound: C-hardness. E.g. if P is NP-hard, P is at least as
hard as SAT
I Upper bound: C membership. E.g. if P ∈ ΣP2 , P is at most as
hard as Shortest Implicant problem.
I Exact complexity: C-completeness

J.-G. Mailly | Non-Deterministic Time

 Bounds of Complexity
36

In some cases, it’s not easy to determine precisely the complexity of

a problem, but we can give lower/upper bounds.
I Lower bound: C-hardness. E.g. if P is NP-hard, P is at least as
hard as SAT
I Upper bound: C membership. E.g. if P ∈ ΣP2 , P is at most as
hard as Shortest Implicant problem.
I Exact complexity: C-completeness
Prove C-completeness: prove hardness (c.f. polynomial functional
reductions) + prove membership

J.-G. Mailly | Non-Deterministic Time

 Certificate: Intuition
37

I “NP algorithm" for SAT.

Algorithm 1 SAT
Input: φ
Let ω be some interpretation
for c a clause in φ do
sat_clause = false
for l a literal in c do
if ω(l) = 1 then
sat_clause = true
end if
end for
if not sat_clause then
return False
end if
end for
return True
J.-G. Mailly | Non-Deterministic Time
 Certificate: Intuition
37

I “NP algorithm" for SAT.

Algorithm 2 SAT
Input: φ
I Non-deterministic guess
Let ω be some interpretation
for c a clause in φ do
sat_clause = false
for l a literal in c do
if ω(l) = 1 then
sat_clause = true
end if
end for
if not sat_clause then
return False
end if
end for
return True
J.-G. Mailly | Non-Deterministic Time
 Certificate: Intuition
37

I “NP algorithm" for SAT.

Algorithm 3 SAT
Input: φ
I Non-deterministic guess
Let ω be some interpretation
for c a clause in φ do I Each execution of the
sat_clause = false algorithm tests a different
for l a literal in c do value of ω
if ω(l) = 1 then
sat_clause = true
end if
end for
if not sat_clause then
return False
end if
end for
return True
J.-G. Mailly | Non-Deterministic Time
 Certificate: Intuition
37

I “NP algorithm" for SAT.

Algorithm 4 SAT
Input: φ
I Non-deterministic guess
Let ω be some interpretation
for c a clause in φ do I Each execution of the
sat_clause = false algorithm tests a different
for l a literal in c do value of ω
if ω(l) = 1 then I If there is one execution that
sat_clause = true returns True, then φ is a
end if positive instance
end for
if not sat_clause then
return False
end if
end for
return True
J.-G. Mailly | Non-Deterministic Time
 Certificate: Intuition
37

I “NP algorithm" for SAT.

Algorithm 5 SAT
Input: φ
I Non-deterministic guess
Let ω be some interpretation
for c a clause in φ do I Each execution of the
sat_clause = false algorithm tests a different
for l a literal in c do value of ω
if ω(l) = 1 then I If there is one execution that
sat_clause = true returns True, then φ is a
end if positive instance
end for I In this case, ω is called a
if not sat_clause then certificate for φ
return False
end if
end for
return True
J.-G. Mailly | Non-Deterministic Time
 Certificate
38

Definition
A certificate (also called a witness) is a word that certifies the answer
to a computation, or certifies the membership of some word in a
language.

Example
I P = “Given a polynomial P, has P at least one root?”. The
instance P(x) = x 2 can be verified with the certificate x = 0:
P(0) = 0.
x = 0 is a certificate that P is a positive instance of P

J.-G. Mailly | Non-Deterministic Time

 Certificate
38

Definition
A certificate (also called a witness) is a word that certifies the answer
to a computation, or certifies the membership of some word in a
language.

Example
I P = “Given a polynomial P, has P at least one root?”. The
instance P(x) = x 2 can be verified with the certificate x = 0:
P(0) = 0.
x = 0 is a certificate that P is a positive instance of P
I P’= “Given a polynomial P, is P(x) positive for all x?” The
instance P 0 (x) = x 2 − 2 can be verified with the certificate
x = −1: P 0 (−1) = (−1)2 − 2 = 1 − 2 = −1 < 0.
x = −1 is a certificate that P 0 is a negative instance of P’

J.-G. Mailly | Non-Deterministic Time

 NP and CONP Membership
39

Proposition
Let P be a problem. Given an instance x of P and a certificate c, if
the problem
P 0 : « Is c a proof that x is a positive instance of P? »
is in P, then P ∈ NP

Proposition
Let P be a problem. Given an instance x of P and c a certificate, if
the problem

P 0 : « Is c a proof that x is a negative instance of P? »

is in P, then P ∈ CONP

J.-G. Mailly | Non-Deterministic Time

 NP and CONP Membership
39

Proposition
Let P be a problem. Given an instance x of P and a certificate c, if
the problem
P 0 : « Is c a proof that x is a positive instance of P? »
is in P, then P ∈ NP

Proposition
Let P be a problem. Given an instance x of P and c a certificate, if
the problem

P 0 : « Is c a proof that x is a negative instance of P? »

is in P, then P ∈ CONP

NP: Problems where checking a solution is easy

CO NP: Problems where checking a counter-example is easy
J.-G. Mailly | Non-Deterministic Time
 Certificate Verification
40

I “NP algorithm" for SAT.

Algorithm 6 SAT
Input: φ
Let ω be some interpretation
for c a clause in φ do
sat_clause = false
for l a literal in c do
if ω(l) = 1 then
sat_clause = true
end if
end for
if not sat_clause then
return False
end if
end for
return True
J.-G. Mailly | Non-Deterministic Time
 Certificate Verification
40

I “NP algorithm" for SAT.

I “P algorithm" for verifying ω

Algorithm 8 SAT
Algorithm 9 Verify Interpretation
Input: φ
Input: φ, ω
Let ω be some interpretation
for c a clause in φ do
for c a clause in φ do
sat_clause = false
sat_clause = false
for l a literal in c do
for l a literal in c do
if ω(l) = 1 then
if ω(l) = 1 then
sat_clause = true
sat_clause = true
end if
end if
end for
end for
if not sat_clause then
if not sat_clause then
return False
return False
end if
end if
end for
end for
return True
return True
J.-G. Mailly | Non-Deterministic Time
 Certificate Verification
40

I “NP algorithm" for SAT.

I “P algorithm" for verifying ω

Algorithm 10 SAT
Algorithm 11 Verify Interpretation
Input: φ
Input: φ, ω
Let ω be some interpretation
for c a clause in φ do
for c a clause in φ do
sat_clause = false
sat_clause = false
for l a literal in c do
for l a literal in c do
if ω(l) = 1 then
if ω(l) = 1 then
sat_clause = true
sat_clause = true
end if
end if
end for
end for
if not sat_clause then
if not sat_clause then
return False
return False
end if
end if
end for
end for
return True
return True
J.-G. Mailly | Non-Deterministic Time
 General C-Membership with a Certificate
41

Proposition
Let P be a problem. Given an instance x of P and a certificate c, if
the problem
P 0 : « Is c a proof that x is a positive instance of P? »

is in ΠPi−1 , then P ∈ ΣPi

J.-G. Mailly | Non-Deterministic Time

 General C-Membership with a Certificate
41

Proposition
Let P be a problem. Given an instance x of P and a certificate c, if
the problem
P 0 : « Is c a proof that x is a positive instance of P? »

is in ΠPi−1 , then P ∈ ΣPi

Proposition
Let P be a problem. Given an instance x of P and a certificate c, if
the problem
P 0 : « Is c a proof that x is a negative instance of P? »
is in ΣPi−1 , then P ∈ ΠPi

J.-G. Mailly | Non-Deterministic Time

 References
42

[Turing 1936] A. M. Turing, On computable numbers, with an

application to the Entscheidungsproblem. Proceedings of the
London Mathematical Society, 1936.
[Cook 1972] S. A. Cook, A Hierarchy for Nondeterministic Time
Complexity. STOC, 187–192, 1972.
[Seiferas et al 1978] J. I. Seiferas, M. J. Fischer and A. R. Meyer,
Separating Non-deterministic Time Complexity Classes. J. ACM,
25.1, 146–167, 1978.
[Stockmeyer 1976] L. J. Stockmeyer, The polynomial-time hierarchy.
Theoretical Computer Science, 3, 1–22, 1976.

J.-G. Mailly | Non-Deterministic Time

 References
43

[Cook 1971] S. A. Cook, The Complexity of Theorem-Proving

Procedures. Proc. of the Third Annual Symposium on Theory of
Computing, 151–158, 1971.
[Karp 1972] R. M. Karp, Reducibility Among Combinatorial
Problems. Proc. of Symposium on the Complexity of Computer
Computations, 85–103, 1972.
[Creignou 1995] N. Creignou, The Class of Problems That are
Linearly Equivalent to Satisfiability or a Uniform Method for
Proving NP-Completeness. Theoretical Computer Science, 145,
111–145, 1995.
[Umans 2001] C. Umans, The Minimum Equivalent DNF Problem
and Shortest Implicants. J. Comput. Syst. Sci., 63, 597–611,
2001.

J.-G. Mailly | Non-Deterministic Time

 References
44

[Aloupis et al. 2015] G. Aloupis, E. D. Demaine, A. Guo and G.

Viglietta, Classic Nintendo games are (computationally) hard.
Theor. Comput. Sci. 586: 135-160, 2015.
[Langerman and Uno 2018] S. Langerman, Y. Uno, Threes!, Fives,
1024!, and 2048 are hard. Theor. Comput. Sci. 748: 17-27, 2018.
[Garey and Johnson 1979] M. R. Garey and D. S. Johnson,
Computers and Intractability: A Guide to the Theory of
NP-Completeness. Freeman, 1979.
[Schaefer and Umans 2002a] M. Schaefer and C. Umans,
Completeness in the Polynomial-Time Hierarchy: A Compendium.
Sigact News September, 2002.
[Schaefer and Umans 2002b] M. Schaefer and C. Umans,
Completeness in the Polynomial-Time Hierarchy: Part II. Sigact
News December, 2002.

J.-G. Mailly | Non-Deterministic Time