Abstract
It is known that provability in propositional intuitionistic logic is Pspace-complete. As Pspace is closed under complements, there must exist a Logspace-reduction from refutability to provability. Here we describe a direct translation: given a formula φ, we define ̅φ so that ̅φ is provable if and only if φ is not.
BibTeX - Entry
@InProceedings{urzyczyn:LIPIcs.TYPES.2020.11,
author = {Urzyczyn, Pawe{\l}},
title = {{Duality in Intuitionistic Propositional Logic}},
booktitle = {26th International Conference on Types for Proofs and Programs (TYPES 2020)},
pages = {11:1--11:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-182-5},
ISSN = {1868-8969},
year = {2021},
volume = {188},
editor = {de'Liguoro, Ugo and Berardi, Stefano and Altenkirch, Thorsten},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13890},
URN = {urn:nbn:de:0030-drops-138901},
doi = {10.4230/LIPIcs.TYPES.2020.11},
annote = {Keywords: Intuitionistic logic, Complexity}
}
|
Keywords: |
|
Intuitionistic logic, Complexity |
|
Collection: |
|
26th International Conference on Types for Proofs and Programs (TYPES 2020) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
07.06.2021 |
Creative Commons Attribution 4.0 International license (CC BY 4.0)