Complete Problems Involving Boolean Labelled Structures and Projection Transactions

Publisher Website
Google Scholar
Abstract
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.

This publication has 0 references indexed in Scilit: