Complexity of the CNF-satisfiability problem
From MaRDI portal
Publication:6300044
arXiv1804.02478MaRDI QIDQ6300044FDOQ6300044
Authors: G. V. Bokov 
Publication date: 6 April 2018
Abstract: This paper is devoted to the complexity of the Boolean satisfiability problem. We consider a version of this problem, where the Boolean formula is specified in the conjunctive normal form. We prove an unexpected result that the CNF-satisfiability problem can be solved by a deterministic Turing machine in polynomial time.
This page was built for publication: Complexity of the CNF-satisfiability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300044)
