2008/05/05 by Jerrald Meek, Meek, Jerrald
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.0805.0517
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
openalex publication_date 2008/05/05 · arxiv created 2008/09/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.