The closure of monadic NP
| Author(s) : | Larry J. Stockmeyer Ronald Fagin Miklos Ajtai, |
| Publisher : | N/A |
| Publication Date : | 1997 |
| ISSN : | N/A |
| Abstract : | It is a well-known result of Fagin that the complexity class NP coincides with the class of problems expressible in existential second-order logic (\Sigma 1 1), which allows sentences consisting of a string of existential second-order quantifiers followed by a first-order formula. Monadic NP is the class of problems expressible in monadic \Sigma 1, |