On the Applicability of Post's Lattice

Details On the Applicability of Post's Lattice On the Applicability of Post's Lattice

2010-07-17

arxiv.org/abs/1007.2924v3

Computer Science

Computational Complexity

Scientific paper

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'.

Affiliated with

Also associated with

No associations

Rating

On the Applicability of Post's Lattice does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Applicability of Post's Lattice, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Applicability of Post's Lattice will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-658959