(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.
Sample Solution
