Analysis of the Deterministic Polynomial Time Solvability of the 0-1-Knapsack Problem

Simple item page
dc.creatorMeek, Jerrald
dc.date2008-05-05
dc.date2008-09-06
dc.date.accessioned2026-07-07T10:00:46Z
dc.date.available2026-07-07T10:00:46Z
dc.descriptionPreviously 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.
dc.description14 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
dc.identifierhttps://arxiv.org/abs/0805.0517
dc.identifierhttp://arxiv.org/abs/0805.0517
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/168416
dc.subjectComputational Complexity
dc.subjectF.2.2
dc.titleAnalysis of the Deterministic Polynomial Time Solvability of the 0-1-Knapsack Problem
dc.typetext

Files

Collections

arXiv