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

**Paolo Liberatore**
*Technical Report, Computing Research Repository (CoRR)*

We study the problem of deciding whether some -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.

@techreport{libe-05-d,
title = {Complexity Issues in Finding Succinct Solutions of
PSPACE-Complete Problems},
year = {2005},
author = {Liberatore, Paolo},
institution = {Computing Research Repository (CoRR)},
number = {cs.AI/0503043},
}

HTTP download.