This discussion assesses your ability to clarify the role of each legally mandated attendee on the Individualized Education Program team. This assessment also supports your achievement of Course Learning Outcome….

## Suppose you are studying the computational complexity of a given problem X. It is known that the boolean satisfiability problem can be reduced to X in polynomial time. In addition, it is known that problem X is in class EXPTIME, as somebody have already developed an algorithm for X that is guaranteed to provide a solution in exponential time. Can it be the case that X is an NP-COMPLETE problem? Justify your answer and, if your answer is “yes,” state what would you need to do to show that X is NP-COMPLETE.

Answer the following questions

1. Prove that the problem of deciding whether a Turing Machine M and a DFA D are such that L(M) = L(D) is undecidable.

2. One technique to show that a decision problem is undecidable is to reduce a known undecidable problem, like the Halting Problem, to the problem of concern. Explain what requirement on that reduction

(besides being a reduction, of course) is fundamental for this approach to work.

3. Prove mathematically that if f(n) ∈ O(g(n)), then f(n) ∈ O(g(n)^2 + c), for any constant c ≥ 0

4. Consider the following two decision problems:

P1: Given a Turing machine T and a string w, are there more than one way (i.e., more than one execution)

the machine T can accept w

P2: Given a Turing machine T and a string w, does T accept w?

Use the fact that problem P2 has already been shown undecidable, to prove that problem P1 is also undecidable.

5. Suppose you are studying the computational complexity of a given problem X. It is known that the boolean satisfiability problem can be reduced to X in polynomial time. In addition, it is known that problem X is in class EXPTIME, as somebody have already developed an algorithm for X that is guaranteed to provide a solution in exponential time. Can it be the case that X is an NP-COMPLETE problem? Justify your answer and, if your answer is “yes,” state what would you need to do to show that X is NP-COMPLETE.

6. Prove formally, via a suitable problem reduction, that the Exact 5SAT problem (i.e., determine the satisfiability of a formula in conjunctive normal form where each clause has exactly five literals) is NP-complete. An informal or incomplete argument will not constitute a proof.

7. One technique to show that a decision problem is NP-hard, is to reduce a known NP-hard problem, such as 3SAT, to the problem of concern. Explain what requirements, and why, on such reduction

are fundamental for the approach to work.

7. Explain briefly why pumping Lemma is is useful and important.