Conference item
Higher-order quantified boolean satisfiability
- Abstract:
-
The Boolean satisfiability problem plays a central role in computational complexity and is often used as a starting point for showing NP lower bounds. Generalisations such as Succinct SAT, where a Boolean formula is succinctly represented as a Boolean circuit, have been studied in the literature in order to lift the Boolean satisfiability problem to higher complexity classes such as NEXP. While, in theory, iterating this approach yields complete problems for k-NEXP for all k > 0, using such i...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 989.9KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.MFCS.2022.33
- Publication website:
- https://drops.dagstuhl.de/opus/volltexte/2022/16831/
Authors
Funding
Bibliographic Details
- Publisher:
- Dagstuhl Publishing
- Host title:
- 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
- Series:
- International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
- Series number:
- 47th
- Journal:
- Leibniz International Proceedings in Informatics More from this journal
- Volume:
- 241
- Article number:
- 33
- Pages:
- 33:1--33:15
- Place of publication:
- Dagstuhl, Germany
- Publication date:
- 2022-08-22
- Acceptance date:
- 2022-07-05
- Event title:
- MFCS
- Event location:
- Vienna, Austria
- Event website:
- https://ac.tuwien.ac.at/mfcs2022/
- Event start date:
- 2022-08-22
- Event end date:
- 2022-08-26
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959772563
Item Description
- Language:
-
English
- Keywords:
- Pubs id:
-
1266565
- Local pid:
-
pubs:1266565
- Deposit date:
-
2022-07-05
Terms of use
- Copyright holder:
- Chistikov et al.
- Copyright date:
- 2022
- Rights statement:
- ©2022 Dmitry Chistikov, Christoph Haase, Zahra Hadizadeh, and Alessio Mansutti; licensed under Creative Commons License CC-BY 4.0
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record