Lucas Noritomi-Hartwig
University of Toronto
March 13, 2024
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 1 / 44
CSC363H5 S – Computability
Tutorial 8
Exercise – L in P?
Define the following language L (where |x| is the length of the string x): |x|
2 L= x∈Σ∗:3|Xk
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 2 / 44
Exercise – L in P?
Define the following language L (where |x| is the length of the string x): |x|
2 L= x∈Σ∗:3|Xk
Lucas Noritomi-Hartwig
CSC363H5 S – Computability
March 13, 2024
Exercise – L in P?
Define the following language L (where |x| is the length of the string x): |x|
2 L= x∈Σ∗:3|Xk
Lucas Noritomi-Hartwig
CSC363H5 S – Computability
March 13, 2024
Exercise – L in P?
Is L ∈ P? Proof.
We construct the polynomial-time decider M for L: M(x):
set sum = 0
iterate n from 1 to (2 to the power of |x|):
add n to sum
if sum is divisible by 3:
ACCEPT else:
Thus, we have proven that L ∈ P.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability
March 13, 2024
Programming Help
Exercise – L in P?
Is L ∈ P? Proof.
We construct the polynomial-time decider M for L: M(x):
set sum = 0
iterate n from 1 to (2 to the power of |x|):
add n to sum
if sum is divisible by 3:
ACCEPT else:
Thus, we have proven that L ∈ P.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability
March 13, 2024
Exercise – L in P?
Is L ∈ P? Proof.
We construct the polynomial-time decider M for L: M(x):
set sum = 0
iterate n from 1 to (2 to the power of |x|):
add n to sum
if sum is divisible by 3:
ACCEPT else:
Thus, we have proven that L ∈ P.
Cringe ↑, why?
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability
March 13, 2024
Exercise – L in P?
Is L ∈ P? Proof.
We construct the polynomial-time decider M for L: M(x):
set sum = 0
iterate n from 1 to (2 to the power of |x|):
add n to sum
if sum is divisible by 3:
ACCEPT else:
Thus, we have proven that L ∈ P.
Cringe ↑, why? Line 2 runs in exponential time with respect to |x|. Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 8 / 44
Exercise – L in P?
Recall that we can write the following:
Xn n(n + 1)
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 9 / 44
Exercise – L in P?
Recall that we can write the following:
k=1 We can rewrite M as follows:
n(n + 1) k=2
set y = 2^|x|
set s = (y * (y + 1)) / 2
if s is divisible by 3:
ACCEPT else:
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability
March 13, 2024
程序代写 CS代考 加微信: cstutorcs
Exercise – L in P?
Recall that we can write the following:
k=1 We can rewrite M as follows:
n(n + 1) k=2
set y = 2^|x|
set s = (y * (y + 1)) / 2
if s is divisible by 3:
ACCEPT else:
Now, we can see that M has a polynomial runtime. Thus, L ∈ P.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 11 / 44
AKS Primality Test
The Agrawal–Kayal–Saxena primality test is a deterministic algorithm that, given n ∈ N, will determine, in polynomial time, if n is prime or composite.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 12 / 44
AKS Primality Test
The Agrawal–Kayal–Saxena primality test is a deterministic algorithm that, given n ∈ N, will determine, in polynomial time, if n is prime or composite. The algorithm is as follows:
# Check if n is a perfect power ifn=a^bforsomea>1andb>1:
return “composite”
Find the smallest r coprime with n s.t. ord_r(n) > log_2(n)^2
return “prime”
for a from 1 to floor(sqrt{totient(r)} * log_2(n))):
if (X + a)^n != X^n + a (mod X^r – 1, n):
return “composite”
return “prime”
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 13 / 44
Code Help
AKS Primality Test
The Agrawal–Kayal–Saxena primality test is a deterministic algorithm that, given n ∈ N, will determine, in polynomial time, if n is prime or composite. The algorithm is as follows:
# Check if n is a perfect power ifn=a^bforsomea>1andb>1:
return “composite”
Find the smallest r coprime with n s.t. ord_r(n) > log_2(n)^2
return “prime”
for a from 1 to floor(sqrt{totient(r)} * log_2(n))):
if (X + a)^n != X^n + a (mod X^r – 1, n):
return “composite”
return “prime”
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 14 / 44
AKS Primality Test
The Agrawal–Kayal–Saxena primality test is a deterministic algorithm that, given n ∈ N, will determine, in polynomial time, if n is prime or composite. The algorithm is as follows:
# Check if n is a perfect power ifn=a^bforsomea>1andb>1:
return “composite”
Find the smallest r coprime with n s.t. ord_r(n) > log_2(n)^2
return “prime”
for a from 1 to floor(sqrt{totient(r)} * log_2(n))):
if (X + a)^n != X^n + a (mod X^r – 1, n):
return “composite”
return “prime”
Runtime: O |n|12.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 15 / 44
Exercise – PRIMES Reducibility
Define the following languages:
PRIMES = {n ∈ N : n is prime},
PRIMESEVENS = PRIMES ∪ {n ∈ N : n is even}.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 16 / 44
Exercise – PRIMES Reducibility
Define the following languages:
PRIMES = {n ∈ N : n is prime},
PRIMESEVENS = PRIMES ∪ {n ∈ N : n is even}. Prove that PRIMES ≤p PRIMESEVENS.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 17 / 44
Exercise – PRIMES Reducibility
Define the following languages:
PRIMES = {n ∈ N : n is prime},
PRIMESEVENS = PRIMES ∪ {n ∈ N : n is even}. Prove that PRIMES ≤p PRIMESEVENS.
We first define our polynomial-time reduction function f : N → N:
(n, AKS(n) returns “prime”
1, AKS(n) returns “composite”
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 18 / 44
Exercise – PRIMES Reducibility
Prove that PRIMES ≤p PRIMESEVENS. Proof.
We first define our polynomial-time reduction function f : N → N:
(n, AKS(n) returns “prime”
1, AKS(n) returns “composite”
Now, we define our characteristic function for PRIMES, p, using that of PRIMESEVENS, pe:
p(n) = pe(f(n))
Thus, we have proven that PRIMES ≤p PRIMESEVENS.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S – Computability March 13, 2024 19 / 44
Exercise – PRIMESEVENS in P?
Consider the following “proof”, which attempts to show that PRIMESEVENS ∈ P:
Consider the following algorithm:
in_PRIMESEVENS(n: int):
if n % 2 == 0:
else if n <= 1:
for k in range(2, n): # Excluding n ifn%k==0:
This runs in O(n) time, as the only for loop iterates from 2 to n. Thus in_PRIMESEVENS is a polynomial-time decider for PRIMESEVENS. □
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 20 / 44
Exercise – PRIMESEVENS in P?
Consider the following “proof”, which attempts to show that PRIMESEVENS ∈ P:
Consider the following algorithm:
in_PRIMESEVENS(n: int):
if n % 2 == 0:
else if n <= 1:
for k in range(2, n): # Excluding n ifn%k==0:
This runs in O(n) time, as the only for loop iterates from 2 to n. Thus in_PRIMESEVENS is a polynomial-time decider for PRIMESEVENS. □
Is this proof epic or cringe?
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 21 / 44
Exercise – PRIMESEVENS in P?
Unfortunately, the “proof” is very cringe 🙁
But do YOU know why?
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 22 / 44
Exercise – PRIMESEVENS in P?
Consider the following algorithm:
in_PRIMESEVENS(n: int):
if n % 2 == 0:
else if n <= 1:
for k in range(2, n): # Excluding n
if n % k == 0:
This runs in O(n) time, as the only for loop iterates from 2 to n. Thus in_PRIMESEVENS is a polynomial-time decider for PRIMESEVENS. □
The problem with this “proof” is that the for-loop takes 2|n| time (if we are considering the length to be that of the binary string representation of n). Thus, the “proof” does not prove that PRIMESEVES ∈ P.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 23 / 44
3-Colouring Problem
The 3-colouring problem for graphs asks the following: Given an undirected, simple graph, is it possible to assign each node one of three colours so that no two adjacent nodes have the same colour?
Figure: The left graph is 3-colourable, while the right map is not. Let f : V → {0,1,2} be a function. We define the language 3C as
3C ={G : G = (V, E) is an undirected, simple graph such that (∀v1,v2 ∈V)[(v1,v2)∈E =⇒ f(v1)̸=f(v2)].}
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 24 / 44
Exercise – 3-Colouring Problem in NP?
Prove that 3C ∈ NP.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 25 / 44
Exercise – 3-Colouring Problem in NP?
Prove that 3C ∈ NP.
To prove that 3C ∈ NP, we will describe a polynomial-time verifier of
Let VER be the verifier of 3C. As input, VER takes the graph
G=(V,E)andafunctionf :V →{0,1,2}. Letn=|V|. Note
that ∀v ∈ V , v can have at most n − 1 incident edges, meaning that |E| ≤ n(n + 1).
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 26 / 44
Exercise – 3-Colouring Problem in NP?
Let VER be the verifier of 3C. As input, VER takes the graph G = (V, E) and afunctionf:V →{0,1,2}. Letn=|V|. Notethat∀v∈V,vcanhaveat
most n − 1 incident edges, meaning that |E| ≤ n(n + 1). 2
For each vi ∈ V , VER iterates through the edges in E, and, where there is an edge (vi,vj) ∈ E, VER compares f(vi) and f(vj). If the two values are equal, it rejects the input. If at the end of all iterations it has not rejected, it accepts the input.
Iterating through all of the vertices in V would be of O(n) time complexity. Iterating through all of the edges in E would take O(n2) time complexity. Therefore, VER ∈ O(n · n2) = O(n3).
Thus, we have proven that 3C ∈ NP by describing a polynomial-time verifier. Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 27 / 44
SAT – Boolean Satisfiability Problem
Let {xk}mk=1 be a set of boolean variables, l⟨i,j⟩(xj) is a literal of boolean variable xj. Let B be a boolean formula defined as follows:
B = ^ _ l⟨i,j⟩(xj) i=1 j ∈Ji
where Ji ⊆ {xk}mk=1. We say that B is in conjunctive normal form as it
is a conjunction of clauses, and where clauses are disjunctions of literals.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 28 / 44
SAT – Boolean Satisfiability Problem
Let {xk}mk=1 be a set of boolean variables, l⟨i,j⟩(xj) is a literal of boolean variable xj. Let B be a boolean formula defined as follows:
B = ^ _ l⟨i,j⟩(xj) i=1 j ∈Ji
where Ji ⊆ {xk}mk=1. We say that B is in conjunctive normal form as it
is a conjunction of clauses, and where clauses are disjunctions of literals.
The boolean satisfiability problem asks the following: Does there exist a boolean mapping function b : {xk}mk=1 → {True, False} such that replacing xj with b(xj ) renders B = True? We define the language SAT:
SAT = {B : B is a satisfiable boolean formula}
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 29 / 44
SAT – Boolean Satisfiability Problem
Example: Of the following, which are satisfiable? • B1 = (¬x1 ∨ ¬x2) ∧ (x1 ∨ x2)
• B2 = (¬x1 ∨ ¬x2) ∧ (x1) ∧ (x2)
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 30 / 44
SAT – Boolean Satisfiability Problem
Example: Of the following, which are satisfiable? • B1 = (¬x1 ∨ ¬x2) ∧ (x1 ∨ x2)
• B2 = (¬x1 ∨ ¬x2) ∧ (x1) ∧ (x2)
• B1 is satisfiable by x1 7→ True and x2 7→ False, or instead by x1 7→ False and x2 7→ True.
• B2 is not satisfiable.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 31 / 44
SAT – Boolean Satisfiability Problem
Example: Of the following, which are satisfiable? • B1 = (¬x1 ∨ ¬x2) ∧ (x1 ∨ x2)
• B2 = (¬x1 ∨ ¬x2) ∧ (x1) ∧ (x2)
• B1 is satisfiable by x1 7→ True and x2 7→ False, or instead by x1 7→ False and x2 7→ True.
• B2 is not satisfiable. Clauses 2 and 3 demand that x1 = x2 = T rue, but clause 1 demands that at least one of x1 or x2 is False.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 32 / 44
SAT – Boolean Satisfiability Problem
Example: Of the following, which are satisfiable? • B1 = (¬x1 ∨ ¬x2) ∧ (x1 ∨ x2)
• B2 = (¬x1 ∨ ¬x2) ∧ (x1) ∧ (x2)
• B1 is satisfiable by x1 7→ True and x2 7→ False, or instead by x1 7→ False and x2 7→ True.
• B2 is not satisfiable. Clauses 2 and 3 demand that x1 = x2 = T rue, but clause 1 demands that at least one of x1 or x2 is False.
Thus, B1 ∈ SAT, but B2 ∈/ SAT.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 33 / 44
3-Colouring Reduction to SAT
Prove that 3C ≤p SAT.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 34 / 44
3-Colouring Reduction to SAT
Prove that 3C ≤p SAT.
Let G = (V,E). To prove that 3C ≤p SAT, we must define a boolean
formula, A such that A ∈ SAT if, and only if, G ∈ 3C.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 35 / 44
3-Colouring Reduction to SAT
Prove that 3C ≤p SAT.
Let G = (V,E). To prove that 3C ≤p SAT, we must define a boolean
formula, A such that A ∈ SAT if, and only if, G ∈ 3C. Proof.
LetG=(V,E),V ={vk}nk=1. Wecreateacollectionofbooleanvariables Ck,i for 1 ≤ k ≤ n, i ∈ {0, 1, 2}, where Ck,i being true is interpreted as “vk has colour i”.
The 3C problem has three conditions that must be met:
1 A1: Each vertex is assigned at least one colour,
2 A2: Each vertex is assigned no more than one colour,
3 A3: Each pair of neighbouring vertices have different colours.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 36 / 44
3-Colouring Reduction to SAT
The 3C problem has three conditions that must be met:
1 A1: Each vertex is assigned at least one colour,
2 A2: Each vertex is assigned no more than one colour,
3 A3: Each pair of neighbouring vertices have different colours.
We write A1 as follows:
A1 = ^ _Ck,i = ^(Ck,0 ∨Ck,1 ∨Ck,2)
k=1 i=0 k=1
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 37 / 44
3-Colouring Reduction to SAT
The 3C problem has three conditions that must be met:
1 A1: Each vertex is assigned at least one colour,
2 A2: Each vertex is assigned no more than one colour,
3 A3: Each pair of neighbouring vertices have different colours.
We write A2 as follows:
A2 = ^ ^Ck,i ∨¬Ck,(i+1) (mod 3) ∨¬Ck,(i+2) (mod 3) k=1 i=0
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 38 / 44
3-Colouring Reduction to SAT
The 3C problem has three conditions that must be met:
1 A1: Each vertex is assigned at least one colour,
2 A2: Each vertex is assigned no more than one colour,
3 A3: Each pair of neighbouring vertices have different colours.
We write A3 as follows:
A3 = ^ ^(¬Ck,i ∨¬Cl,i)
(vk ,vl )∈E i=0
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 39 / 44
3-Colouring Reduction to SAT
Thus, we have found our boolean formula, A, that is satisfiable if, and only if, G is 3–colourable, to be:
A=A1 ∧A2 ∧A3 =A1 ∧A3 ∧A2
"n #"2 #
= ^(Ck,0 ∨Ck,1 ∨Ck,2) ∧ ^ ^(¬Ck,i ∨¬Cl,i)
k=1 (vk ,vl )∈E i=0
∧ ^ ^Ck,i ∨¬Ck,(i+1) (mod 3) ∨¬Ck,(i+2) (mod 3) k=1 i=0
Therefore, we have proven that 3C ≤p SAT.
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 40 / 44
The k-clique problem asks the following: Given an undirected, simple graph, G, and a non-negative integer k, does there exist a subgraph of G that is a k-clique?
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 41 / 44
The k-clique problem asks the following: Given an undirected, simple graph, G, and a non-negative integer k, does there exist a subgraph of G that is a k-clique?
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 42 / 44
SAT and k-Clique
Prove that SAT ≤p k-clique
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 43 / 44
SAT and k-Clique
Prove that SAT ≤p k-clique Diagram:
Lucas Noritomi-Hartwig (UofT) CSC363H5 S - Computability March 13, 2024 44 / 44