Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming

Here we study linear programming applied to the random K-SAT problem, a fundamental problem in computational complexity. The K-SAT problem is to decide whether a Boolean formula with N variables and structured as a conjunction of M clauses, each being a disjunction of K variables or their negations...

Descripción completa

Detalles Bibliográficos
Autores principales: Schawe, Hendrik, Bleim, Roman, Hartmann, Alexander K.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2019
Materias:
Research Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6474652/
https://www.ncbi.nlm.nih.gov/pubmed/31002678
http://dx.doi.org/10.1371/journal.pone.0215309

Internet

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6474652/
https://www.ncbi.nlm.nih.gov/pubmed/31002678
http://dx.doi.org/10.1371/journal.pone.0215309

Ejemplares similares