Analysis of the Deterministic Polynomial Time Solvability of the 0-1-Knapsack Problem
arXiv:0805.0517
Abstract
Previously the author has demonstrated that a representative polynomial search partition is required to solve a NP-complete problem in deterministic polynomial time. It has also been demonstrated that finding such a partition can only be done in deterministic polynomial time if the form of the problem provides a simple method for producing the partition. It is the purpose of this article to demonstrate that no deterministic polynomial time method exists to produce a representative polynomial search partition for the Knapsack problem.
14 Pages; The author is delaying submission for publication so that counter arguments may be proposed. ftp://ftp%40micrognu%2ecom:anon%[email protected]/pnenp/knapsack.pdf