2002/08/12 by C. Sauerbier, Sauerbier, C.
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #F.1.1 #F.2.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.cs/0208018
openalex publication_date 2002/08/12 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
This paper considers the question of P = NP in context of the polynomial time SAT algorithm. It posits proposition dependent on existence of conjectured problem that even where the algorithm is shown to solve SAT in polynomial time it remains theoretically possible for there to yet exist a non-deterministically polynomial (NP) problem for which the algorithm does not provide a polynomial (P) time solution. The paper leaves open as subject of continuing research the question of existence of instance of conjectured problem.