Planar NAE3SAT is in P
Bernard M. E. Moret · ACM SIGACT News · 1988
Lichtenstein proposed the use of a "planar" version of 3SAT as a departure point for proofs of NP -completeness that would at once prove the general graph problem as well as its restriction to planar graphs to be NP -complete. Dyer and Frieze later proved that Planar lin3SAT is also NP -complete. Of the three standard versions of 3SAT, only NAE3SAT remained open. We provide a very simple reduction from NAE3SAT to Simple MaxCut, which respects Lichtenstein's conditions; since it is known that the planar version of (Simple) MaxCut is in P, so is the planar version of NAE3SAT, thereby setting the question (if in a somewhat unexpected way).