- Exercises proposed during lessons of the Academic Year 2020/21
- Problem Examples from Virtuale 20/21
- Problems from Exam 06/26/2020
- Exercise Book
- Flashcards to learn theory
Prove the uncompatibility of the halting problem, namely the fact that the function 
defined by cases:
- equal to 1 if
terminates - equal to 0 otherwise
is uncomputable.
Solutions: We show that from an hypothetical machine computing halt, calling it Mhalt, we can get another TM, call Muc, which computes the uc, and we know it cannot exist (uc is by definition a function not computable by any TM).
Let us construct Muc out of Mhalt:
- on input α Muc proceeds by calling Mhalt on input (α, α) and:
- in case Mhalt returns 0 (meaning that Mα(α) diverges), Muc outputs 1
- otherwise, i.e. in the case in which Mhalt returns 1 (meaning that Mα(α) converges), Muc knows that it can safely call U (the universal TM) on (α, α) and that U will terminate its execution on that input (because what U does with input (α, α) is to simulate the execution of Mα(α)), returning an output b. Now:
- if b=1 then Muc returns 0
- if b=0 then Muc returns 1
- Muc as we have just defined it is indeed a TM computing uc, but since we know that uc is uncomputable, there is a contradiction and halt itself is uncomputable.
Show that the function inc: N -> N such that inc(n) = n+1 can be computed in linear time by giving an explicit construction of a TM.
Solution: At first we have to encode natural numbers as binary strings. We have two possibility:
- traditional encoding: (e.g. 12 = 1100)
- reverse encoding: (e.g. 12 = 0011)
If we choose to use reverse encoding the problem is quite simple. With a single tape TM we will need to pass through the whole input string from left to right only once, meaning in linear time. The transition function will look as follows:
(qinit, ▷) → (q0, ▷, R)
(q0, 0) → (q1, 1, L)
(q0, 1) → (q0, 0, R)
(q0, □) → (q1, 1, L)
(q1, 0) → (q1, 0, L)
(q1, 1) → (q1, 1, L)
(q1, ▷) → (qhalt, ▷, S)
Write a TM which computes the sum of two binary numbers a,b >= 0.
Write a TM for palindromes, i.e. a TM that accepts a binary string w iff w is a palindrome.
The alphabet Γ can be defined as {▷, 0, 1, □}, while the set of states Q is {qinit, qa, q0, q0a, q1, q1a, qb, qhalt}. The transition function δ is specified as follows:
(qinit, ▷) → (qa, ▷, R)
(qa, 0) → (q0, ▷, R)
(qa, 1) → (q1, ▷, R)
(qa, □) → (qhalt, □, S)
// 0 is read
(q0, 0/1) → (q0, 0/1, R)
(q0, □) → (q0a, □, L)
(q0a, 0) → (qb, □, L)
(q0a, ▷) → (qa, ▷, R)
// 1 is read
(q1, 0/1) → (q1, 0/1, R)
(q1, □) → (q1a, □, L)
(q1a, 1) → (qb, □, L)
(q1a, ▷) → (qa, ▷, R)
//
(qb, 0/1) → (qb, 0\1, L)
(qb, ▷) → (qa, ▷, R)
This is not exactly the same proposed by professor, but I've tested it with JFLAP and it works. Here it is my implementation. Keep in mind that in JFLAP Touring Machines start with the head pointing at the first character of the string. Also the string is not preceded by the starting character ▷, but it is fully surrounded with □. So I have replaced ▷ with x and I've made some changes to manage the different starting position of the head.
Write a TM that accept a binary string w iff the number of 0s in w is equal to the number of 1s in w.
This was proposed as a homework problem, so there is no solution showed in class, but I've tested mine with JFLAP and it works. As usual, keep in mind that in JFLAP Touring Machines start with the head pointing at the first character of the string. Also the string is not preceded by the starting character ▷, but it is fully surrounded with □. So I have replaced ▷ with x and I've made some changes to manage the different starting position of the head.
Solution: The alphabet Γ can be defined as {▷, 0, 1, □}, while the set of states Q is {qinit, qa, qb, q0, q1, qhalt}. The transition function δ is specified as follows:
(qinit, ▷) → (qa, □, R)
(qa, 0) → (q0, ▷, R)
(qa, 1) → (q1, ▷, R)
(qa, ▷) → (qa, ▷, R)
(qa, □) → (qhalt, □, S)
(q0, 0) → (q0, 0, R)
(q0, 1) → (qb, ▷, L)
(q0, ▷) → (q0, ▷, R)
(q1, 0) → (qb, ▷, L)
(q1, 1) → (q1, 1, R)
(q1, ▷) → (q1, ▷, R)
(qb, 0/1/▷) → (qb, 0/1/▷, L)
(qb, □) → (qa, □, R)
Determine which ones of the following problems are decidable:
- P = {M | L(M) infinite}
- P = {M | PALINDROME ⊆ L(M)}
- P = {M | M has exactly 5 states}
- P = {M | L(M) = Ø}
- P = Ø
Claim: P is undecidable.
Proof: By Rice's Theorem:
- P is non-trivial:
- P ≠ Ø: if M is a TM that accepts every string, then L(M) is infinite, so it belongs to P.
- ∃ M | M ∉ P: if L(M) = Ø (so M is a TM which rejects every input), then |L(M)| = 1, so L(M) is not infinite, and so M not belongs to P.
- P is extensional: Assume L(M) = L(N) and M ∈ P. We have to show that also N ∈ P. Since M ∈ P iff |L(M)| = ∞, and considering that L(M) = L(N) ⇒ |L(M)| = |L(N)|, then |L(N)| = ∞ ⇒ N ∈ P. QED.
Claim: P is undecidable.
Proof: By Rice's Theorem:
- P is non-trivial:
- P ≠ Ø: if M is the TM accepting every string, then PALINDROME ⊆ L(M), and so M belongs to P.
- ∃ M | M ∉ P: if L(M) = {01} (which can be easily decided with a TM M), then L(M) not contains PALINDROME, so M not belongs to P.
- P is extensional: Assume L(M) = L(N) and M ∈ P. We have to show that also N ∈ P. Since M ∈ P iff PALINDROME ⊆ L(M) , we know that PALINDROME ⊆ L(M) = L(N), so PALINDROME ⊆ L(N), then N ∈ P. QED.
Claim: P is decidable.
Proof: Trying to apply Rice's Theorem we can easily see that P is non-trivial, but is not extensional. To demonstrate that it is decidable we have to design a TM that decides P. Decided a binary encoding for a TM, our TM take in input a string w and it checks that w is a valid encoding. If w is invalid then it is rejected. Otherwise w is accepted iff it encodes a TM with exactly 5 states.
Claim: P is undecidable
Proof: By Rice's Theorem:
- P is non-trivial:
- P ≠ Ø: if M is the TM rejecting every string, then L(M) = Ø, and so M belongs to P.
- ∃ M | M ∉ P: if M is the TM acceppting every binary string, then L(M) = {0,1}* ≠ Ø, so M not belongs to P.
- P is extensional: Assume L(M) = L(N) and M ∈ P. We have to show that also N ∈ P. Since M ∈ P iff L(M) = Ø, we know that Ø = L(M) = L(N), so L(N) = Ø, then N ∈ P. QED.
Claim: P is decidable
Proof: Trying to apply Rice's Theorem instantly fails because P is trivial. Indeed P = Ø by definition. To show that P is decidable we have to design a TM that decides P and such a TM is the TM rejecting every input string.
Prove that the function minmax which given a list of natural numbers {a1, a2, ..., an} returns both the minimum and the maximum between a1, a2, ..., an in in FP
Solutions: We can describe the solution of this problem with a pseudocode:
input: (a1, a2, ..., an) appropriately encoded
output: (min, max)
min = a1 # 1 instruction
max = a1 # 1 instruction
for i <- 2 to n: # For loop executed O(n) times. it contains at most 4 instructions
if ai < min:
min = ai
if ai > max:
max = ai
return (min, max) # 1 instruction
- The total number of executed instructions is 2 + 4*O(n) + 1 = O(n).
- The size of the intermediate results can be bound as follows:
- min and max, being elements of the input list, are of course smaller or equal to the length of the input
- i, going to 2 to n, is of course smaller or equal to the input.
- Each instruction executed by the algorithm takes polynomial time. Indeed, we have:
- assignments
- comparison between natural numbers of polynomial length.
Altogether, this means that the described algorithm works in polynomial time, and this mean that the function minmax belongs to FP.
Solutions provided are not official solutions by professor, but are made by me. So be careful.
Construct a deterministic TM of the kind you prefer, which decides the following language:
Study the complexity of TM you have defined.
The alphabet Γ can be defined as {▷, 0, 1, □}, while the set of states Q is {qinit, q1, q2, q3, qhalt}. The transition function δ is specified as follows:
(qinit, ▷) → (q1, ▷, S)
(q1, ▷) → (q1, ▷, R)
(q1, 0) → (q2, 0, R)
(q1, 1) → (q1, 1, R)
(q2, 0) → (q2, 0, R)
(q1, □) → (q3, □, L)
(q2, □) → (q3, □, L)
(q3, 0) → (q3, 0, L)
(q3, 1) → (q3, 1, L)
(q3, ▷) → (qhalt, ▷, S)
If the TM reaches the ending state qhalt, then the string is accepted, otherwise, when the TM reaches a state where δ is not defined, the string is rejected.
Note that there are no transitions for the configuration (q2, 1), which corresponds to substring 01 detected.
When the TM read □ (i.e. the input string is finished), it goes to the state q3, in which it simply goes back to the starting position (the cell with ▷) and then it passes to the state qhalt, terminating and accepting the string.
It follows a JFLAP implementation. As usual, keep in mind that in JFLAP Touring Machines start with the head pointing at the first character of the string. Also the string is not preceded by the starting character ▷, but it is fully surrounded with □. So I've made some changes to manage the different starting position of the head.
You are required to prove that the following function f is in FP. To do that, you can give a TMs or define some pseudocode. The function is one that, given a list L=L1,…,Ln, returns its inverse, namely Ln,Ln−1,…,L1.
First, we define a pseudocode that compute f:
def f (L=[L1,L2,...,Ln]):
Reverse = new List[n]
for i in range(n):
Reverse[i] = L[n-1-i]
return Reverse
Now we have to prove that this algorithm works in polynomial time. To do this we have to:
- encode the input as a binary string. Our analysis of the time complexity will be done with respect of the length l of such a string;
- prove tha the number of instructions is bounded by a polynomial function in l;
- prove that each instruction can be simulated by a TM in polynomial time
- show that all the "intermediate" data and results use a space bounded by a polynomial function in l.
Step 1: In order to encode L = [L1, L2, Ln] we need at first to encode its components Li. We can do it with one of the standards encoding of natural numbers in {0,1}*. Since using n bits allows us to encode 2^n - 1 numbers, the encoding of Li requires log(Li) + 1 bits.
Now we need to encode the whole list L. To do that we introduce a separator character # between elements of the list and then we encode 1 as 11, 0 as 00 and # as 01. So the total encoding will have length:
Step 2: The only relevant instruction is Reverse[i] = L[n-1-i] which is executed n times, which is polynomial. Other instructions (updating i and similar) have also a polynomial bound and can be trivially translated in a polynomial number of TM steps.
Step 3: Let's suppose to have a TM with two tapes. On the first we have the input (L), on the second one we write the output. Let's suppose that the head of the first tape it's in the first cell (the one before the input) and the head of the second tape it is in the first blank cell after the output written until this moment.
To execute Reverse[i] = L[n-1-i] we need to move the head of the input tape until the end of the string (□ read) which takes at most l steps, then we have to go back until we read 01 (the binary encoding for the separator #) which takes around l/n steps.
Now we can copy what we read in the first tape on the second tape, replacing all the cells in the first tape with □, which takes again around l/n steps. Then we have to move the first head on the first cell again: l steps in the worst case.
This algorithm, which is far to be the most efficient, takes 2l + 2l/n steps, which is polynomial in l.
Step 4: We never use more than l cells in each tape.
We studied the problem CLIQUE. You are required to classify the subset THREECLIQUE of CLIQUE consisting of all the pairs (G,3). To which class does THREECLIQUE belong?
THREECLIQUE is a way simpler problem than CLIQUE. In fact we can solve it with the algorithm described by this simple pseudocode:
def threeclique(V, E):
for u in V:
for v in V - {u}:
for w in V - {u, v}:
if (u,v), (v,w) and (u,w) belongs to E:
return true
return false
Checking if an edge belongs to the set of edges of the graph can be done by simpling comparing it with alle the m edges of the graph, which can be done in polynomial time.
This operation is inside a triple nested for, so it will be done a very big number of times, but still polynomial. SO the problem belongs to the P class.
Let f, g be the functions defined as 
and 
.
Select one or more.
In Turing Machines:
Select one or more.
- The presence of many tapes can make the class P different
- What can be computed in exponential time is different from what can be computed in polynomial time
- The presence of many tapes can make the class DTIME(n) different
- The class EXP can be equal to P
The problem 3SAT is:
Select one or more.
- Such that INDSET can be reduced to it
- NP-hard
- In the class EXP
- Computable in polynomial time
Suppose a language L is both in NP and in EXP. Then
Select one or more.
- EXP and NP are necessarily equal.
- L can even be NP-complete.
- NP and EXP are maybe different.
- L cannot be in P.
The notion of PAC-learnable concept class:
Select one or more.
- Needs to hold for every distribution D on the instance class.
- Does not make any reference to the time complexity of the learning algorithm.
- Requires the output concept to have probability of error ε, in all cases.
- Cannot be reached when the underlying concept class is the one conjunctions of literals.
Give a TM to decide L= set of strings for which if 01 is present, then is followed by all 0s.
The alphabet Γ can be defined as {▷, 0, 1, □}, while the set of states Q is {qinit, q1, q2, qhalt}. The transition function δ is specifies as follows:
(qinit, ▷) → (q1, ▷, S)
(q1, ▷) → (q1, ▷, R)
(q1, 0) → (q2, 0, R)
(q1, 1) → (q1, 1, R)
(q2, 0) → (q2, 0, R)
(q2, 1) → (q3, 1, R)
(q3, 0) → (q3, 0, R)
(q1, □) → (q4, □, L)
(q2, □) → (q4, □, L)
(q3, □) → (q4, □, L)
(q4, 0) → (q4, 0, L)
(q4, 1) → (q4, 1, L)
(q4, ▷) → (qhalt, ▷, S)
If the TM reaches the ending state qhalt, then the string is accepted, otherwise, when the TM reaches a state where δ is not defined, the string is rejected.
States explanation:
- qinit: it is just the initial state. The TM immediately passes to q1.
- q1: the TM read the string character by character. If it read 0, it passes to q2.
- q2: as q1, but a 0 has been detected yet, so reading a 1 will mean that 01 is detected and the TM will pass to q3.
- q3: 01 detected, so the TM only reads 0s, indeed there are no transitions for the configuration (q3, 1).
- q4: This state is reached when the TM reads a blank character, meaning that the string is finished and has to be accepted. It just reset the head at the start of the tape, before passing to qhalt, which is the final state.
When the TM read □ (i.e. the input string is finished), it goes to the state q3, in which it simply goes back to the starting position (the cell with ▷) and then it passes to the state qhalt, terminating and accepting the string.
Prove that the problem is in NP: check if a number is the sum of powers of 3 by giving a TM or pseudocode. (Asked to the professor, he said that 3^0 is not allowed as the problem would be trivial).
We at first notice that a number can be expressed as a sum between power of 3 (3 to the power of 0 excluded) iff it is divisible by 3. Since we have to show that the problem is in NP we can describe a non-deterministic algorithm. So our algorithm can just pick a random number non-deterministically, multiply it by 3 and check if it is equal to the input number n. The multiplication and the comparison between two numbers can be of course executed in polynomial time. The pseudocode is the following:
def f(n):
assign non-deterministically a number greater than 0 to k
k = k * 3
return k == n
PP is the set of theorems expressed in the Principia Matematica, published by Bertrand Russel in 1909-13. Do they fall in a complexity class? Motivate
This formulation of the problem (which is indeed a reformulation by a student) is actually a bit tricky and it would require to know all the algorithm of the book to establish to which subset of NEXP the algorithms belong (NEXP is a set enough big to make us quite sure that all the algorithms in that book belong to it).
However, I've found similar exercises with the original formulations of the professor, which are more clear. The problem asks to establish which is the complexity of establishing if an algorithm (which is given in input with some binary codification) belongs to PP.
This can be achieved comparing (in linear time) it with all the algorithms of the book (which are a constants number), so of course is a P problem.
PDF containing exercises and some solutions by the professors.
Solutions made by us of the exercises of the PDF follow.
We are basically psudo-coding a linear search. The first thing we'll have to do is encoding the input as binary strings. This is pretty straightforward: we can introduce a separator # that separates the elements of the list, and finally, the query.
The list would therefore be encoded as 
.
Now, we know that the saving of a given natural number requires 
bits, and our encoding will be the following: 0=00,1=11,#=01.
This means that every normal bit will require twice the space, and we will have n separators occupying 2 bits each.
We can now introduce the pseudocode solving the problem:
def linsearch(List[Int] l, int query) {
i = 0
while i < |l| {
if (l[i] == query) {
return i
}
}
return -1
}
Now, the analysis of the code. We know that the first instruction is 
. The while loop, then, is executed at most |l| times, and contains three (the while check, the if, the return) constant instructions. The final instruction is still constant.
This means that, finally: 
.
The intermediate results are clearly bounded: the list will never exceed its original size (nor get modified) and i is an int.
Since n is clearly polynomial, we have proven the presence in FP.
A TM could simulate this code by simply having the same input we cited before, as , scrolling to the end of the TM, copying the query to another tape, then searching for the element while saving the index in a third tape (incremented at every separator).
We know that a language is in NP when:
Therefore, we can introduce a TM 
that verifies the language 
and a TM 
that verifies 
. Now, if we introduce a third TM that, given a triple 
emulates the first one on 
and the second one on 
, ultimately returning 1 if and only if both the emulations do so.