Die u:cris Detailansicht:
Satisfiability-unsatisfiability transition in the adversarial satisfiability problem
- Autor(en)
- Marco Bardoscia, Daniel Nagaj, Antonello Scardicchio
- Abstrakt
Adversarial satisfiability (AdSAT) is a generalization of the satisfiability (SAT) problem in which two players try to make a Boolean formula true (resp. false) by controlling their respective sets of variables. AdSAT belongs to a higher complexity class in the polynomial hierarchy than SAT, and therefore the nature of the critical region and the transition are not easily parallel to those of SAT and worthy of independent study. AdSAT also provides an upper bound for the transition threshold of the quantum satisfiability problem (QSAT). We present a complete algorithm for AdSAT, show that 2-AdSAT is in P, and then study two stochastic algorithms (simulated annealing and its improved variant) and compare their performances in detail for 3-AdSAT. Varying the density of clauses α we claim that there is a sharp SAT-UNSAT transition at a critical value whose upper bound is αc 1.5, suggesting a much stricter upper bound for the QSAT transition than those previously found.
- Organisation(en)
- Quantenoptik, Quantennanophysik und Quanteninformation
- Externe Organisation(en)
- Abdus Salam International Centre for Theoretical Physics, Istituto Nazionale di Fisica Nucleare (INFN), Roma, Slovenian Academy of Sciences and Arts
- Journal
- Physical Review E
- Band
- 89
- Anzahl der Seiten
- 10
- ISSN
- 1539-3755
- DOI
- https://doi.org/10.1103/PhysRevE.89.032128
- Publikationsdatum
- 03-2014
- Peer-reviewed
- Ja
- ÖFOS 2012
- 103036 Theoretische Physik, 103025 Quantenmechanik
- Schlagwörter
- ASJC Scopus Sachgebiete
- Condensed Matter Physics, Statistical and Nonlinear Physics, Statistics and Probability
- Link zum Portal
- https://ucrisportal.univie.ac.at/de/publications/6a852c7e-65bb-4bb4-952d-a8f0a65d65b1