About this document
Polynomial Witnesses for Non-Satisfiable 3CNF by colosal227 is a document available to read on EtoBox.
The paper investigates the non-satisfiability of random 3CNF formulas, establishing that for formulas with a clause density greater than cn7/5, polynomial size witnesses for non-satisfiability exist. The authors extend spectral techniques to show that these witnesses can be found in time 2O(n log n). The study contributes to the broader understanding of the complexity of the 3SAT problem and its implications for co-NP and P.
- Author
- colosal227
- Language
- EN