2011/12/06 by Christian Laus, Laus, Christian, Dirk Oliver Theis +1
Computer Science · Mathematics · #68Q87 #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Data Management and Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:68Q87
paper · pdf · doi:10.48550/arxiv.1112.1360
12 pages
arxiv created 2011/12/06 · openalex publication_date 2011/12/06 · arxiv updated 2011/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Regular signed SAT is a variant of the well-known satisfiability problem in which the variables can take values in a fixed set V ⊂ [0,1], and the `literals' have the form "x ≤ a" or "x ≥ 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.