Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems

Simple item page
dc.creatorLiberatore, Paolo
dc.date2005-03-18
dc.date2005-03-29
dc.date.accessioned2026-07-07T03:22:44Z
dc.date.available2026-07-07T03:22:44Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/cs/0503043
dc.identifierhttp://arxiv.org/abs/cs/0503043
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32665
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectLogic in Computer Science
dc.subjectI.2.3; I.2.4; I.2.8; F.1.3; F.2.2
dc.titleComplexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems
dc.typetext

Files

Collections

arXiv