Random Thoughts.....What Are You Thinking?

1. Define polynomial time

Algorithm A runs in polynomial time if there is a polynomial p such that for every x, the call A(x) halts in at mostp(|x|) steps.

2. How does one prove, straightforwardly, that an algorithm runs in polynomial time?

One can straightforwardly prove that an algorithm runs in polynomial time by counting the largest possible number of operations executed for an input of unknown size n. If this formula is a polynomial, then the algorithm runs in polynomial time.

3. What is the largest possible number of operations that can be executed in the following algorithm, on an input stack S of size n? Count the number of calls to the operators :=, push, top, pop, not, is_empty, =, and return.

algorithm Palindrome(stack<int> S)
// returns True if S is a palindrome and False otherwise, destroying its input in the process
begin
// create two reversed copies of the reverse of S, in T1 and T2, while destroying S
stack<int> T1 := empty
stack<int> T2 := empty
while not is_empty(S):
push(top(S),T1)
push(top(S),T2)
pop(S)
// now destroy T1 and restore S
while not is_empty(T1):
push(top(T1),S))
pop(T1)
// Now S is back to its original value, and T2 is the reverse of S.
// Check if S = T2
while not is_empty(S):
if not top(S)= top(T2): return False
return True
end

Solution:
Let n be the length of S. The first 2 assignments always happen. Each iteration of the loop body executes five instructions for a total of 5n inside the loop body. Additionally the expressopm not is_empty(S) in the loop guard is executed n+1 times, for a total of 2n+2 function calls (counting both not's and is_empty's). Similarly, the next loop executes 3n instructions in the loop body and 2n+2 function calls in the loop guard. In the worst case, the final loop executes n times, each doing a not, two tops, and a comparison (but NOT a return), for a total of 4n function calls in the loop body and 2n+2 in the loop guard. Finally we have 1 return instruction. The total then is

2+(5n+2n+2) + (3n+2n+2) + (4n+2n+2) + 1

for a total of 18n+9 instructions and function calls.


4. Define class P

Predicate R is in class P if there is a polynomial time algorithm A that decides R.

5. What is the point of studying class P?

Class P is a mathematical formulation of the notion of the intuitive notion of tractability, in the same way that general recursiveness is a mathematical forumlation of the intuitive notion of computability. (Tractable means, roughly speaking, computable in a reasonable amount of time).

6 How does one prove, straightforwardly, that a predicate is in class P?

The straightforward way to prove that a predicate is in class P is go implement it by a polynomial time algorithm.

7. Define class NP

Predicate p is in class NP if there is a polynomial-time algorithm A and a polynomial q such that (1) if p(x) is true then there is some string y of length less than or equal to q(|x|) such that A(x,y) returns true, and (2) if p(x) is false then there is no such string.

8. Give the alternative characterication of class NP in terms of nondetermistic algorithms:

Theorem: A predicate p is in class NP if there is a nondeterministic algorithm A and a polynomial q such that (1) whenever p(x) is true, A(x) has an execution path that returns true in q(|x|) or fewer steps, and (2) A(x) never has a path that returns true when p(x) is false.

9. Prove that the predicate SAT is in class NP using the theorem stated in question 8.

11. State the definitions of NP-hard and NP-complete.

12. State the Cooke-Levin Theorem.

13. Name five of of Karp's 21 NP-complete problem, and describe three of those five. Write your descriptions so that anyone who has had a course in discrete math can understand it precisely.

14. Describe a basic method to show that a predicate is undecidable.

Solution: To show that p is undecidable, implement a solution to a problem that is already known to be undecidable (e.g., the halting problem) that calls p as a helper, and in which all other components can be implemented.

15. Describe the basic method to show that a a problem is NP-complete.

Solution: To show that given problem is NP-complete, one can do the following two steps:
Show that your problem is in NP by writing an algorithm A as described in the definition of NP-completeness (or in the alternative characterization)
Write a polynomial time pseudocode algorithm that decides a known NP-complete problem (such as SAT), all of whose helper functions are in class P except for your problem.
Note this is conceptually similar to the technique for showing that a problem is undecidable.

16. What is the practical significance of showing that a predicate is in class NP-complete?

Answer: Practically speaking, you should not expect to implement a polynomial time algorithm for it -- or, even more intuitively, an algorithm that runs for large inputs in a reasonable amount of time.

17. Give the signatures of NP-complete and polynomial time

Solution:

NP-complete: predicate -> Bool
polynomial time : algorithm -> Bool