Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems

Details Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems

2005-03-18

arxiv.org/abs/cs/0503043v3

Computer Science

Artificial Intelligence

Scientific paper

We study the problem of deciding whether some PSPACE-complete problems have models of bounded size. Contrary to problems in NP, models of PSPACE-complete problems may be exponentially large. However, such models may take polynomial space in a succinct representation. For example, the models of a QBF are explicitely represented by and-or trees (which are always of exponential size) but can be succinctely represented by circuits (which can be polynomial or exponential). We investigate the complexity of deciding the existence of such succinct models when a bound on size is given.

Affiliated with

Also associated with

No associations

Rating

Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems 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 Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-502249