Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the behaviour of random K-SAT on trees
Stockholm University, Faculty of Science, Department of Physics.
2012 (English)In: Journal of Statistical Mechanics: Theory and Experiment, ISSN 1742-5468, E-ISSN 1742-5468, P05009- p.Article in journal (Refereed) Published
Abstract [en]

We consider the K-satisfiability problem on a regular d-ary rooted tree. For this model, we demonstrate how we can calculate in closed form the moments of the total number of solutions as a function of d and K, where the average is over all realizations for a fixed assignment of the surface variables. We find that different moments pick out different 'critical' values of d, below which they diverge as the total number of variables on the tree -> infinity and above which they decay. We show that K-SAT on the random graph also behaves similarly. We also calculate exactly the fraction of instances that have solutions for all K. On the tree, this quantity decays to 0 (as the number of variables increases) for any d > 1. However, the recursion relations for this quantity have a non-trivial fixed point solution which indicates the existence of a different transition in the interior of an infinite rooted tree.

Place, publisher, year, edition, pages
2012. P05009- p.
Keyword [en]
solvable lattice models, exact results, random graphs, networks, typical-case computational complexity
National Category
Physical Sciences Applied Mechanics
Identifiers
URN: urn:nbn:se:su:diva-80087DOI: 10.1088/1742-5468/2012/05/P05009ISI: 000305266900011OAI: oai:DiVA.org:su-80087DiVA: diva2:555365
Note

AuthorCount:2;

Available from: 2012-09-19 Created: 2012-09-12 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Krishnamurthy, Supriya
By organisation
Department of Physics
In the same journal
Journal of Statistical Mechanics: Theory and Experiment
Physical SciencesApplied Mechanics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf