This assignment consists of two parts.

1. Write a 2 page position paper which either defends 
   or argues against the "efficient computation thesis";
   that is, the identifcation of the intuitive concept of 
   "efficient or feasible computation" with the mathematically
   well defined concept of "computable by a Turing machine within
   polynomial time". In particular, your argument
   should adcdress issues such as 
   a) How appropriate is the Turing machine model in this regard?
   b) Why polynomial time?
   c) What are the consequences of accepting or rejecting this thesis?

2. Suppose you have an algorithm which uses 
   T(N,W,V)) = polynomial(N, log W, log V) 
   steps to solve the knapsack decision problem when there are N items,
   the knapsack bound is (at most) W and the desired value is (at least) V. 
   (Note: if such an algorithm existed,
   then P = NP.)
   Show how to solve the knapsack optimization problem in polynomial(N)
   steps. That is, we want to skecth a polynomial time reduction
   of the optimization problem to the decision problem. If possible,
   give a more precise complexity time bound in terms of the input
   $(w_1,v_1), (w_2,v_2), ....(w_N,v_N); W}. How does your bound depend
   on n and the size of the inputs?