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=...

Description complète

Enregistré dans:
Détails bibliographiques
Auteurs principaux: Raffaele Marino, Giorgio Parisi, Federico Ricci-Tersenghi
Format: article
Langue:EN
Publié: Nature Portfolio 2016
Sujets:
Science
Q
Accès en ligne:https://doaj.org/article/719c06fe184d4189855a85415a4443c4
Tags: Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
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

Documents similaires