Normal Forms for Second-Order Logic over Finite Structures, and Classification of NP Optimization Problems
- Thomas Eiter ,
- Georg Gottlob ,
- Yuri Gurevich
Annals of Pure and Applied Logic |
We prove a new normal form for second-order formulas on finite structures and simplify the Kolaitis-Thakur hierarchy of NP optimization problems.