QCSP on partially reflexive forests

Details QCSP on partially reflexive forests QCSP on partially reflexive forests

2011-03-31

arxiv.org/abs/1103.6212v1

Computer Science

Computational Complexity

Scientific paper

We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive forests. We obtain a complexity-theoretic dichotomy: QCSP(H) is either in NL or is NP-hard. The separating condition is related firstly to connectivity, and thereafter to accessibility from all vertices of H to connected reflexive subgraphs. In the case of partially reflexive paths, we give a refinement of our dichotomy: QCSP(H) is either in NL or is Pspace-complete.

Affiliated with

Also associated with

No associations

Rating

QCSP on partially reflexive forests 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 QCSP on partially reflexive forests, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QCSP on partially reflexive forests will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-245713