2008/08/24 by Jerrald Meek, Meek, Jerrald
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.2.0 #FOS: Computer and information sciences #Optimization and Packing Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.0808.3222
12 Pages; ftp://ftp%40micrognu%2Ecom:anon%[email protected]/pnenp/conclusion.pdf
openalex publication_date 2008/08/24 · arxiv created 2008/09/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This is the final article in a series of four articles. Richard Karp has proven that a deterministic polynomial time solution to K-SAT will result in a deterministic polynomial time solution to all NP-Complete problems. However, it is demonstrated that a deterministic polynomial time solution to any NP-Complete problem does not necessarily produce a deterministic polynomial time solution to all NP-Complete problems.