On the lower bounds of random Max 3 and 4-SAT
2018
A k-CNF formula is said to be p-satisfiable if there exists a truth assignment satisfying a fraction of \(1-2^{-k}+p2^{-k}\) of its clauses. We obtain better lower bounds for random 3 and 4-SAT to be p-satisfiable. The technique we use is a delicate weighting scheme of the second moment method, where for every clause we give appropriate weight to truth assignments according to their number of satisfied literal occurrences.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
0
Citations
NaN
KQI