Complete on Average Boolean Satisfiability |
| |
| Authors: | Jie Wang |
| |
| Institution: | Department of Computer Science, University of Massachusetts, One University Avenue, Lowell, Massachusetts, 01854, f1, http://www.cs.uml.edu/˜wang |
| |
| Abstract: | We present in this paper a dynamic binary coding scheme α on CNF formulas ψ, and show that under a uniform distribution μα on binary string α(ψ), SAT is complete on average, where μα(ψ) is proportional to α(ψ)−22−α(ψ). We then show that there is k0>2 such that for all kk0, kSAT under μα is complete on average. |
| |
| Keywords: | average NP-completeness distributional tiling distributional Boolean satisfiability randomized reductions |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
