The Complexity of Propositional Implication

Details The Complexity of Propositional Implication The Complexity of Propositional Implication

2008-11-06

arxiv.org/abs/0811.0959v3

Computer Science

Computational Complexity

Scientific paper

10.1016/j.ipl.2009.06.015

The question whether a set of formulae G implies a formula f is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae that are built from a systematically restricted set of Boolean connectives. We give a complete complexity classification for all sets of Boolean functions in the meaning of Post's lattice and show that the implication problem is efficentily solvable only if the connectives are definable using the constants {false,true} and only one of {and,or,xor}. The problem remains coNP-complete in all other cases. We also consider the restriction of G to singletons.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Propositional Implication 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 The Complexity of Propositional Implication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Propositional Implication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-630806