Analysis of the Deterministic Polynomial Time Solvability of the 0-1-Knapsack Problem
Abstract
Description
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%40anon@ftp.micrognu.com/pnenp/knapsack.pdf
14 Pages; The author is delaying submission for publication so that counter arguments may be proposed. ftp://ftp%40micrognu%2ecom:anon%40anon@ftp.micrognu.com/pnenp/knapsack.pdf