About this document
Planar 3-SAT and NP-Completeness by Steven Miltenburg is a document available to read on EtoBox.
This paper defines planar boolean formulae and demonstrates that the set of true quantified planar formulae is polynomial space complete while the set of satisfiable planar formulae is NP-complete. It provides proofs of NP-completeness for planar node cover, planar Hamiltonian circuit, and geometric connected dominating set, as well as polynomial space completeness for planar generalized geography. The results are achieved through a novel crossover box technique that simplifies the proofs for various planar
- Author
- Steven Miltenburg
- Language
- EN