Semi decidability and complexity

(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

The post Semi decidability and complexity appeared first on homework handlers.