| Complexity of several constraint-satisfaction problems using the heuristic classical algorithm WalkSAT. | |
| | |
MedLine Citation:
|
PMID: 21867108 Owner: NLM Status: In-Data-Review |
Abstract/OtherAbstract:
|
We determine the complexity of several constraint-satisfaction problems using the heuristic algorithm WalkSAT. At large sizes N, the complexity increases exponentially with N in all cases. Perhaps surprisingly, out of all the models studied, the hardest for WalkSAT is the one for which there is a polynomial time algorithm. |
| | |
Authors:
|
Marco Guidetti; A P Young |
Related Documents
:
|
21707328 - The international index of erectile function: a methodological critique and suggestions... 21813358 - L(p)-l(q) penalty for sparse linear and sparse multiple kernel multitask learning. 19447068 - Microbial communities in industrial environment. 10065058 - Do we all mean the same thing by "problem-based learning"? a review of the concepts and... 18948428 - Agency, relatedness, inner peace, and problem solving in sexual offending: how sexual o... 11895238 - A schematic approach to diagnosing and resolving lecturalgia. |
Publication Detail:
|
Type: Journal Article Date: 2011-07-06 |
Journal Detail:
|
Title: Physical review. E, Statistical, nonlinear, and soft matter physics Volume: 84 ISSN: 1550-2376 ISO Abbreviation: Phys Rev E Stat Nonlin Soft Matter Phys Publication Date: 2011 Jul |
Date Detail:
|
Created Date: 2011-08-26 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101136452 Medline TA: Phys Rev E Stat Nonlin Soft Matter Phys Country: United States |
Other Details:
|
Languages: eng Pagination: 011102 Citation Subset: IM |
Affiliation:
|
Dipartimento di Fisica, Università di Ferrara and INFN-Sezione di Ferrara, Ferrara, Italy and Department of Physics, University of California, Santa Cruz, California 95064, USA. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Single-file diffusion of particles with long-range interactions: Damping and finite-size effects.
Next Document: Crossover between structured and well-mixed networks in an evolutionary prisoner's dilemma game.