Theory of Computing – Examples
v.0.7 - 21/2/2024
Michele Amoretti
Quantum Information Science
University of Parma
Contents
1 Information Theory 1
1.1 Entropy – Horse Racing . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Mutual Information – Binary Symmetric Channel . . . . . . . . . . . 1
1.3 Kolmogorov Complexity – Find the Random String . . . . . . . . . . 2
2 Computability 2
2.1 Mapping Reducibility vs. Turing Reducibility . . . . . . . . . . . . . 2
2.2 AT M is not mapping reducible to AT M . . . . . . . . . . . . . . . . . 2
3 Computational Complexity 3
3.1 GCD – Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . 3
3.2 NP-Complete Problems . . . . . . . . . . . . . . . . . . . . . . . . . 3
Quantum Information Science
University of Parma
Parco Area delle Scienze
43124 Parma
Italy
[Link]
Preface
This is a collection of examples related to the Theory of Computing
part of the High Performance Computing course ([Link]. in Computer
Engineering, University of Parma).
1
1 Information Theory
1.1 Entropy – Horse Racing
Let us consider eight horses with win probabilities { 12 , 14 , 81 , 16
1 1 1 1 1
, 64 , 64 , 64 , 64 }. To
communicate the race winner, we may use 3 bits, as to enumerate the eight horses
we need actually 3 bits. However, taking into account the fact that the horses have
different probabilities of being announced as winners, we may choose a clever binary
representation, namely:
0, 10, 110, 1110, 111100, 111101, 111110, 111111.
In this way, the average description length is 2 bits.
Let’s now compute the entropy of the random variable X representing win an-
nouncements:
1 1 1 1
H(X) = − log − log ... = 2 bits (1)
2 2 4 4
We know that entropy is the average amount of information produced by a
stochastic source of data. With this example, we have seen that the entropy of a
random variable can be also interpreted as the lower bound on the average number
of bits required to represent the random variable.
1.2 Mutual Information – Binary Symmetric Channel
Let us consider a noisy channel where an input bit b is received as b̄ with probability
p (as b with probability 1−p), as illustrated in Fig. 1. This model, denoted as Binary
Symmetric Channel, is the most simple model of noisy channel. Let us call X the
random variable representing the transmitted bits, and Y the one representing the
received bits. Their mutual information is
I(X; Y ) = H(Y ) − H(Y |X) = H(Y ) − Hb (p) (2)
where Hb (p) is the binary entropy. The previous equation can be proved by observing
that {Y |X = x} is a Bernoulli random variable (when x is transmitted, the value of
Y is x with probability 1 − p and x̄ with probability p).
Figure 1: Binary Symmetric Channel model.
The channel capacity is
C = max I(X; Y ) = max H(Y ) − Hb (p) (3)
p(x) p(x)
1.3 Kolmogorov Complexity – Find the Random String 2
To compute C, we observe that H(Y ) is maximized to 1 when X has uniform
distribution (p(x) s.t. p(0) = p(1) = 12 ), for which also Y has uniform distribution
independently of p (the proof is left for exercise). On the other hand, Hb (p) does
not depend on p(x). Therefore, the channel capacity turns out to be:
C = 1 − Hb (p) = 1 + p log p + (1 − p) log(1 − p) (4)
We can observe that, when p = 0 or p = 1, then C = 1. The minimum capacity,
C = 1/2, arises when p = 1/2.
1.3 Kolmogorov Complexity – Find the Random String
Tell if the following strings are Kolmogorov random:
33333333333
31415926535
84354279521
They all have the same probability 10−11 of being randomly extracted from the set
of 11-digit strings. However, C(x) < 11 for the first string (which is {3}11 ) and also
for the second one (which is π · 1010 ). Only the last string is Kolmogorov random,
having C(x) = 11.
2 Computability
2.1 Mapping Reducibility vs. Turing Reducibility
Let us recall the definition of mapping reducibility:
A ≤m B ⇔ [w ∈ A ⇔ f (w) ∈ B]. (5)
This definition implies that, given w, there is a Turing Machine M B that computes
f (w) and, thanks to the oracle for B, tells whether f (w) ∈ B, i.e., w ∈ A. This
means that M B can decide A, i.e., that A ≤T B. In conclusion, mapping reducibility
implies Turing reducibility.
Instead, Turing reducibility does not imply mapping reducibility. Indeed, Turing
reducibility means that there is an oracle Turing machine M B able to decide A. This
definition does not imply the existence of f () such that w ∈ A ⇔ f (w) ∈ B.
2.2 AT M is not mapping reducible to AT M
Let us define the language
AT M = {(M, w)|M is a TM and M rejects w}. (6)
We know that AT M is Turing-recognizable by a Universal Turing machine (UTM).
Now we prove that AT M is not Turing-recognizable.
3
If both languages were Turing-recognizable, then AT M would be decidable, i.e.,
there would exist a TM that halts for all (M, w). Since we know that AT M is not
decidable, the initial assumption was wrong.
Now observe that, being AT M not Turing-recognizable, there is no f () such that
[(M, w) ∈ AT M ⇔ f (M, w) ∈ AT M ]. To have such an f (), we would need a Turing
machine that recognizes AT M .
We conclude that AT M is not mapping reducible to AT M .
3 Computational Complexity
3.1 GCD – Euclidean Algorithm
Let us consider two positive integers a and b.
1. Find q0 and r0 s.t. a = q0 b + r0 .
2. Find q1 and r1 s.t. b = q1 r0 + r1 .
3. Repeatedly solve ri = qi+2 ri+1 + ri+2 until rn = 0.
4. GCD(a, b) = rn−1 .
Exercise: find GCD(125, 75) using the Euclidean Algorithm.
3.2 NP-Complete Problems
• SAT. Given n Boolean variables x1 , .., xn , is there at least one configuration
of the variables s.t. f (x1 , .., xn ) = 1?
• 3SAT. Given n Boolean variables x1 , .., xn and a set of clauses that each one
relates at most 3 variables, is there at least one configuration of the variables
s.t. the clauses evaluate to 1?
• CircuitSAT. Given n Boolean variables x1 , .., xn and a set of clauses xi+1 =
fi (x1 , .., xi ) with i ≥ n, is there at least one configuration of the variables s.t.
the clauses evaluate to 1?
• Map Coloring. Are k colors sufficient to color an arbitrary map so that no
two adjacent features have the same color? With k = 2, the answer can be
found in polynomial time in the number of features (it is sufficient to find a
vertex with an odd number of incident edges). With k ≥ 4, it is always possible
to color the map so that no two adjacent features have the same color. With
k = 3, the problem is NP-Complete.
• 3-Partition. Given 3n numbers, decide whether they can be split into triples
of equal sum.
• Bin Packing. We have an unlimited number of bins each of capacity B, and
n objects of sizes s1 , s2 , etc. s.t. 0 < si ≤ B. Given k, is there a packing using
no more than k bins?
3.2 NP-Complete Problems 4
• Traveling Salesman Problem (TSP). Given a graph and an integer B, is
there a cycle through all the vertices such that the total weight of the edges
used is at most B?
REFERENCES 5
References
[1] S. Arora, B. Barak, Computational Complexity – A Modern Ap-
proach Cambridge University Press, 2009.