Skip Navigation

Journal of Logic and Computation 1994 4(4):337-357; doi:10.1093/logcom/4.4.337
© 1994 by Oxford University Press
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by STEWART, I. A.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Original Articles

Logical Description of Monotone NP Problems

IAIN A. STEWART

Department of Computer Science, University of Swansea Swansea, SA2 8PP, UK E-mail: i.a.stewart{at}swansea.ac.uk

We introduce the class of problems NPC-RAT accepted by polynomial time (nondeterministic) conjunctive random-access Turing machines (C-RATs): such machines crash when the oracle answers ‘no’ (the oracle is always the input structure). We show that NPC-RAT consists of all monotone problems in NP and we logically characterize this complexity class in two ways: the first involves an extension of first-order logic using an operator corresponding to some problem (an approach initiated by Immerman); the second involves a restricted version of existential second-order logic (in the style of Fagin). In both logics, symbols belonging to the problem vocabulary are only allowed to occur positively. We also show that NPC-RAT possesses complete problems via monotone projection translations. It had previously been shown that certain complete problems for NP (via logspace reductions) are unlikely to be complete for NP via monotone projection translations.

Keywords: Descriptive complexity theory,; monotone problems,; computational complexity,; NP.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 J Logic ComputationHome page
A. Arratia and C. E. Ortiz
Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
J Logic Computation, December 1, 2006; 16(6): 817 - 840.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.