CS 611 Fall 2011
Take-Home Midterm Exam

This exam is due at 5 p.m. Friday, October 21. It is worth 75 points.

Procedures

You may turn in this exam either in paper form, or via e-mail.

If in paper form, then place answers to the exercises below, stapled, and labeled with your name, in my box in 202 Chapman.

If via e-mail, then send answers to the exercises below to ggchappell@alaska.edu, using the subject “WMID”.

• Your answers should consist of a text or wordprocessor file. This should be attached to your e-mail message.
• Be sure to include your name in your e-mail.
• I may not read your exam e-mail immediately. If you wish to discuss the exam (or anything else) with me, send me a separate message with a different subject line.

Exercises (75 pts total)

1. What exactly is meant by each of the following?
   1. Computational complexity.
   2. Decision problem.
   3. Instance.
   4. The class P.
   
    
2. In this class, the choice of encoding scheme for a problem generally does not matter, as long as the scheme is “reasonable”.
   1. Why not? Hint: Your answer should involve the concept of a polynomial.
   2. Give an example of a problem and two different encoding schemes for it (which do not need to be described in extreme detail), so that the choice of encoding scheme does affect the computational complexity of the problem, but does not impact the issues we concentrate on in this class.
   
    
3. In each part, an argument is given. If the argument is essentially correct, then say so. Otherwise, explain the error.
   1. Suppose that a problem lies in P. Then there is a polynomial-time algorithm that solves it. Running this algorithm is one way to certify that a “yes” answer to the problem, is correct. Therefore, every problem in P, also lies in NP.
   2. Suppose that a problem lies in NP. If an instance has a “yes” answer, then there is a certificate of this that can be checked in polynomial time. Checking such a certificate is one way to determine whether the answer to the problem is “yes”, and so there is a polynomial-time algorithm to solve the problem. Therefore, every problem in NP, also lies in P.
   
    
4. Prove that the following decision problem “1-IN-3 SAT” is NP-complete.

   Problem: 1-IN-3 SAT.

   Instance: An instance of 3SAT.

   Question: Is there a truth assignment for the variables so that each clause in the instance contains exactly one true literal?
    

5. Suppose that tomorrow someone were to publish a polynomial-time algorithm to solve the Hamiltonian Cycle problem (HC). Briefly explain the major ways in which this would change what is known about computational complexity.
    
6. The problem CLIQUE is only known to be NP-complete if the number k (the number of vertices in the clique we are looking for) is part of the instance. Explain. What happens if k is a fixed value?
    
7. Give an example of a function that is not computable.
    
8. Our definition of NP-completeness required that every problem in NP reduces to the given problem. Yet, when we prove a problem to be NP-complete, we generally only reduce one such problem. How can this be good enough?
    
9. If A and B are decision problems, and we have a Karp reduction from A to B, then we say—somewhat informally—that B is at least as hard as A. Explain why we say this.