Loading...
Please wait, while we are loading the content...
Similar Documents
Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems
| Content Provider | arXiv |
|---|---|
| Author | Liberatore, Paolo |
| Date of Submission | 2005-03-29 |
| Abstract | 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. |
| Related Links | https://arxiv.org/pdf/cs/0503043.pdf |
| arXiv | cs/0503043 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Artificial Intelligence Computer Science - Computational Complexity Computer Science - Logic in Computer Science Deduction and Theorem Proving Knowledge Representation Formalisms and Methods Problem Solving, Control Methods, and Search Complexity Measures and Classes Nonnumerical Algorithms and Problems Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
