✦ LIBER ✦

Monotonicity and the Expressibility of NP Operators

✍ Scribed by Iain A. Stewart

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 517 KB
Volume: 40
Category: Article
ISSN: 0044-3050
DOI: 10.1002/malq.19940400118

No coin nor oath required. For personal study only.

✦ Synopsis

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 L^NP^. 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.

📜 SIMILAR VOLUMES

On the Monotonicity of Positive Linear O

On the Monotonicity of Positive Linear Operators

✍ M.Kazim Khan; B. Della Vecchia; A. Fassih 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 377 KB

We provide sufficient conditions for a sequence of positive linear approximation operators, L n ( f, x), converging to f (x) from above to imply the convexity of f. We show that, for the convolution operators of Feller type, K n ( f, x), generated by a sequence of iid random variables taking values

Representable Monotone Operators and Lim

Representable Monotone Operators and Limits of Sequences of Maximal Monotone Operators

✍ Yboon García; Marc Lassonde 📂 Article 📅 2011 🏛 Springer Netherlands 🌐 English ⚖ 341 KB

Monotonicity of the inverse of weakly el

Monotonicity of the inverse of weakly elliptic differential operators

✍ Gerd Herzog; Roland Lemmert 📂 Article 📅 2003 🏛 Springer 🌐 English ⚖ 119 KB

The sum of a maximal monotone operator o

The sum of a maximal monotone operator of type (FPV) and a maximal monotone operator with full domain is maximal monotone

✍ Liangjin Yao 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 241 KB

Enlargements and sums of monotone operat

Enlargements and sums of monotone operators

✍ Julian P. Revalski; Michel Théra 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 124 KB

The Range of a Monotone Operator

✍ S. Simons 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 265 KB