Affordable Access

On the Applicability of Post's Lattice

Authors
  • Thomas, Michael
Type
Preprint
Publication Date
Jan 05, 2012
Submission Date
Jul 17, 2010
Source
arXiv
License
Yellow
External links

Abstract

For decision problems P defined over Boolean circuits from a restricted set of gates, we have that P(B) AC0 many-one reduces to P(B') for all finite sets B and B' of gates such that all gates from B can be computed by circuits over gates from B'. In this paper, we show that a weaker version of this statement holds for decision problems defined over Boolean formulae, namely that P(B) NC2 many-one reduces to P(B' union {and,or}) and that P(B) NC2 many-one reduces to P(B' union {false,true}), for all finite sets B and B' of Boolean functions such that all f in B can be defined in B'.

Report this publication

Statistics

Seen <100 times