On the satisfiability of random regular signed SAT formulas
From MaRDI portal
Publication:6229529
arXiv1112.1360MaRDI QIDQ6229529FDOQ6229529
Authors: Christian Laus, Dirk Oliver Theis 
Publication date: 6 December 2011
Abstract: Regular signed SAT is a variant of the well-known satisfiability problem in which the variables can take values in a fixed set V subset [0,1], and the `literals' have the form "x le a" or "x ge a". We answer some open question regarding random regular signed k-SAT formulas: the probability that a random formula is satisfiable increases with |V|; there is a constant upper bound on the ratio m/n of clauses m over variables n, beyond which a random formula is asypmtotically almost never satisfied; for k=2 and V=[0,1], there is a phase transition at m/n=2.
This page was built for publication: On the satisfiability of random regular signed SAT formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6229529)
