The backtracking survey propagation algorithm for solving random K-SAT problems

The backtracking survey propagation algorithm for solving random K-SAT problems

The K-satisfability problem is a combinatorial discrete optimization problem, which for K=3 is NP-complete, and whose random formulation is of interest for understanding computational complexity. Here, the authors introduce the backtracking survey propagation algorithm for studying it for K=3 and K=...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Raffaele Marino, Giorgio Parisi, Federico Ricci-Tersenghi
Formato: article
Lenguaje:EN
Publicado: Nature Portfolio 2016
Materias:
Science
Q
Acceso en línea:https://doaj.org/article/719c06fe184d4189855a85415a4443c4
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
id oai:doaj.org-article:719c06fe184d4189855a85415a4443c4
record_format dspace
spelling oai:doaj.org-article:719c06fe184d4189855a85415a4443c42021-12-02T14:40:15ZThe backtracking survey propagation algorithm for solving random K-SAT problems10.1038/ncomms129962041-1723https://doaj.org/article/719c06fe184d4189855a85415a4443c42016-10-01T00:00:00Zhttps://doi.org/10.1038/ncomms12996https://doaj.org/toc/2041-1723The K-satisfability problem is a combinatorial discrete optimization problem, which for K=3 is NP-complete, and whose random formulation is of interest for understanding computational complexity. Here, the authors introduce the backtracking survey propagation algorithm for studying it for K=3 and K=4.Raffaele MarinoGiorgio ParisiFederico Ricci-TersenghiNature PortfolioarticleScienceQENNature Communications, Vol 7, Iss 1, Pp 1-8 (2016)
institution DOAJ
collection DOAJ
language EN
topic Science
Q
spellingShingle Science
Q
Raffaele Marino
Giorgio Parisi
Federico Ricci-Tersenghi
The backtracking survey propagation algorithm for solving random K-SAT problems
description The K-satisfability problem is a combinatorial discrete optimization problem, which for K=3 is NP-complete, and whose random formulation is of interest for understanding computational complexity. Here, the authors introduce the backtracking survey propagation algorithm for studying it for K=3 and K=4.
format article
author Raffaele Marino
Giorgio Parisi
Federico Ricci-Tersenghi
author_facet Raffaele Marino
Giorgio Parisi
Federico Ricci-Tersenghi
author_sort Raffaele Marino
title The backtracking survey propagation algorithm for solving random K-SAT problems
title_short The backtracking survey propagation algorithm for solving random K-SAT problems
title_full The backtracking survey propagation algorithm for solving random K-SAT problems
title_fullStr The backtracking survey propagation algorithm for solving random K-SAT problems
title_full_unstemmed The backtracking survey propagation algorithm for solving random K-SAT problems
title_sort backtracking survey propagation algorithm for solving random k-sat problems
publisher Nature Portfolio
publishDate 2016
url https://doaj.org/article/719c06fe184d4189855a85415a4443c4
work_keys_str_mv AT raffaelemarino thebacktrackingsurveypropagationalgorithmforsolvingrandomksatproblems
AT giorgioparisi thebacktrackingsurveypropagationalgorithmforsolvingrandomksatproblems
AT federicoriccitersenghi thebacktrackingsurveypropagationalgorithmforsolvingrandomksatproblems
AT raffaelemarino backtrackingsurveypropagationalgorithmforsolvingrandomksatproblems
AT giorgioparisi backtrackingsurveypropagationalgorithmforsolvingrandomksatproblems
AT federicoriccitersenghi backtrackingsurveypropagationalgorithmforsolvingrandomksatproblems
_version_ 1718390361597935616

Ejemplares similares