(a) Let n > 0 be an integer and Ln be the language of all linear equations
a1X1 + a2X2 + · · · + anXn + an+1 = 0
in n unknowns X1, X2, . . . , Xn and over integer coefficients a1, a2, . . . , an, an+1,
which have a solution in the integers.
(i) Show that Ln is semi-decidable by describing, in general mathematical terms,
an algorithm that takes as input a linear equation
a1X1 + a2X2 + · · · + anXn + an+1 = 0
with a1, a2, . . . , an, an+1 in the integers, and halts exactly when this equation
has a solution in the integers.
(ii) We now use the fact (stated in the lectures) that Ln is actually decidable.
Describe an algorithm, using a decider for Ln as a subroutine, which for any
linear equation
a1X1 + a2X2 + · · · + anXn + an+1 = 0,
with a1, a2, . . . , an, an+1 in the integers, decides whether or not it has an integer
solution, and if it does, finds at least one such solution.
(b) Argue that the following languages over the alphabet {a, b, c} belong to the
complexity class P. It is enough to give an implementation level description of
the relevant Turing machines, and explain why their complexity is polynomial.
(i) {w ∈ {a, b, c}
∗
| |w|a = |w|b = |w|c}
(ii) {w ∈ {a, b, c}
∗
| it is not the case that |w|a = |w|b = |w|c} Note that we use the notation |w|a to denote the number of occurrences of the letter
a in w, and similarly for |w|b and |w|c.
0 comments