|
NeuroCOLT |
Neural Networks and Computational Learning Theory |
||||||||
|
|
NeuroCOLT Technical Report NC-TR-94-008
Generalized Knapsack Problems Felipe
Cucker Abstract One weaker form of the P \not= NP problem consists of fixing the degree of the polynomial bounds for deterministic and nondeterministic time. The problem obtained in that way, to determine whether DTIME(O(n^d)) = NTIME(O(n^d)) has been solved in the Boolean setting only for the special case d=1. In the context of real Turing machines the question of whether nondeterministic time is more powerful than deterministic time for fixed degree polynomial time bounds also arises naturally. As a first result one can remark that the quoted result for the Boolean situation still holds in the real case since the Knapsack problem can be solved in linear nondeterministic time while it is known that it has an \Omega(n^2) lower bound for deterministic time. This paper shows that in this context a stronger result holds; namely, that for each d \geq 1 the inclusion DTIME(O(n^d))\subset NTIME(O(n^d)) is strict.
Download Compressed Postscript
|