Exact location of the phase transition for random (1,2)-QSAT

DOI10.1051/ITA/2014025zbMath1327.68129OpenAlexW1971527654MaRDI QIDQ5245725

Raphaël Rossignol, Nadia Creignou, Uwe Egly, Hervé Daudé

Publication date: 15 April 2015

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2014025

zbMATH Keywords

phase transitionsharp thresholdsatisfiabilityrandom quantified formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Random 2-SAT and unsatisfiability
• The scaling window of the 2-SAT transition
• Asymptotic Estimates of Stirling Numbers
• New Results on the Phase Transition for Random Quantified Boolean Formulas
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• On the critical exponents of random k‐SAT
• Random 2-SAT: Results and problems

This page was built for publication: Exact location of the phase transition for random (1,2)-QSAT