2010/01/19 by Bernd Schuh, Bernd R. Schuh, Schuh, Bernd R.
Computer Science · Engineering · #Computational Complexity (cs.CC) #Engineering and Test Systems #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Software Reliability and Analysis Research #Software Testing and Debugging Techniques #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.1001.3263
arxiv created 2010/01/19 · openalex publication_date 2010/01/19 · arxiv updated 2010/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Whether the satisfiability of any formula F of propositional calculus can be determined in polynomial time is an open question. I propose a simple procedure based on some real world mechanisms to tackle this problem. The main result is the blueprint for a machine which is able to test any formula in conjunctive normal form (CNF) for satisfiability in linear time. The device uses light and some electrochemical properties to function. It adapts itself to the scope of the problem without growing exponentially in mass with the size of the formula. It requires infinite precision in its components instead.