SAT is as Hard as Solving Homogeneous Diophantine Equation of Degree Two

EasyChair Preprint 9354, version history

Version	Date	Pages	Version notes
1	November 23, 2022	3
2	December 3, 2022	3	We extend the paper's result.
3	December 9, 2022	4	Improved the abstract.
4	March 5, 2023	5	We changed the title to make explicit the result and we introduced a software implementation.
5	March 7, 2023	5	We changed the image in the pdf since we used less verbose software in the output.
6	March 10, 2023	5	Included the developed SAT PY project as an application to this algorithm
7	March 13, 2023	5	Update the SAT PY committed.
8	March 13, 2023	5	Made a whole python implementation in the last repository
9	March 15, 2023	5	Made the constraints on binary integers on the project SAT PY
10	March 16, 2023	5	We removed the commit information from the references of the repositories
11	March 21, 2023	5	Fixed minor details
12	April 17, 2023	5	We have removed the Python Project.
13	September 10, 2023	6	We improved the paper to be consider for peer-review
14	September 11, 2023	6	We improved the abstract.
15	November 21, 2023	6	Polynomial solution to SAT

Keyphrases: Boolean formula, completeness, complexity classes, polynomial time

BibTeX entry

BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:

@booklet{EasyChair:9354,
  author    = {Frank Vega},
  title     = {SAT is as Hard as Solving Homogeneous Diophantine Equation of Degree Two},
  howpublished = {EasyChair Preprint 9354},
  year      = {EasyChair, 2023}}