Determining satisfiability of 3-SAT in polynomial time

Autor:	Flint, Ortho, Wickramasinghe, Asanka, Brasse, Jason, Fowler, Christopher
Rok vydání:	2019
Předmět:	Computer Science - Data Structures and Algorithms 68R05 F.2.2
Druh dokumentu:	Working Paper
Popis:	In this paper, we provide a deterministic polynomial time algorithm that determines satisfiability of 3-SAT. The complexity analysis for the algorithm takes into account no efficiency and yet provides a low enough bound, that efficient versions are practical with respect to today's hardware. We accompany this paper with a serial version of the algorithm without non-trivial efficiencies (link: polynomial3sat.org). Comment: The ninth version is the version submitted to peer review. ArXiv does not allow antiquated versions to be removed
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1903.10081 Zobrazit plný text záznamu View this record from Arxiv