Skip Navigation

Journal of Logic and Computation 1991 1(6):861-882; doi:10.1093/logcom/1.6.861
© 1991 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

Complete Problems Involving Boolean Labelled Structures and Projection Transactions

IAIN A. STEWART

Computing Laboratory, University of Newcastle-upon-Tyne Claremont Road, Newcastle-upon-Tyne NE1 7RU, UK

We show that the classes of the polynomial hierarchy have complete problems via projection translations (without successor) and we exhibit some new, natural complete problems for the complexity classes co-NP and IIp2 via projection translations: these problems were not even known to be complete for co-NP and IIp2 via polynomial-time reductions. Most of the problems involve the reliability of networks of processors where the links may fail and where these failures may be related to one another in a restricted way, but we show how our trick of labelling discrete structures with Boolean literals can be applied to yield other new natural complete problems involving digraphs and Boolean formulae. We also show that it is unlikely that certain problems (known to be complete for the respective complexity class via projection translations) are complete for L, NL, and NP via monotone projection translations; for if any of them are then L = NP, NL = NP, or NP = co-NP.

Keywords: Finite model theory; descriptive complexity theory; complete problems; polynomial hierarchy; network reliability


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
I. A. Stewart
Logical and Complexity-theoretic Aspects of Models of Computation with Restricted Access to Arrays
J Logic Computation, July 24, 2008; (2008) exn025v1.
[Abstract] [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.