| Abstract: | We investigate why similar extensions of first-order logic using operators (that is, generalized quantifiers) corresponding to NP-complete decision problems apparently differ in expressibility: the logics capture either NP or LNP. It had been conjectured that the complexity class captured is NP if and only if the operator is monotone. We show that this conjecture is false. However, we provide evidence supporting a revised conjecture involving finite variations of monotone problems. Mathematics Subject Classification: 68Q15, 03D15, 03C13. |
