Proof Compression and NP Versus PSPACE II: Addendum
Lew Gordeev; Edward Hermann Haeusler
Bulletin of the Section of Logic (2022)
- Volume: 51, Issue: 2, page 197-205
- ISSN: 0138-0680
Access Full Article
top
How to cite
topLew Gordeev, and Edward Hermann Haeusler. "Proof Compression and NP Versus PSPACE II: Addendum." Bulletin of the Section of Logic 51.2 (2022): 197-205. <http://eudml.org/doc/298956>.
@article{LewGordeev2022,
author = {Lew Gordeev, Edward Hermann Haeusler},
journal = {Bulletin of the Section of Logic},
keywords = {graph theory; natural deduction; computational complexity},
number = {2},
pages = {197-205},
title = {Proof Compression and NP Versus PSPACE II: Addendum},
url = {http://eudml.org/doc/298956},
volume = {51},
year = {2022},
}
TY - JOUR
AU - Lew Gordeev
AU - Edward Hermann Haeusler
TI - Proof Compression and NP Versus PSPACE II: Addendum
JO - Bulletin of the Section of Logic
PY - 2022
VL - 51
IS - 2
SP - 197
EP - 205
KW - graph theory; natural deduction; computational complexity
UR - http://eudml.org/doc/298956
ER -
References
top- S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press (2009).
- L. Gordeev, E. H. Haeusler, Proof Compression and NP Versus PSPACE, Studia Logica, vol. 107(1) (2019), pp. 55–83, DOI: https://doi.org/10.1007/s11225-017-9773-5
- L. Gordeev, E. H. Haeusler, Proof Compression and NP Versus PSPACE II, Bulletin of the Section of Logic, vol. 49(3) (2020), pp. 213–230, DOI: https://doi.org/10.18778/0138-0680.2020.16
- E. H. Haeusler, Propositional Logics Complexity and the Sub-Formula Property, [in:] Proceedings of the Tenth International Workshop on Developments in Computational Models DCM (2014), URL: https://arxiv.org/abs/1401.8209v3
- J. Hudelmaier, An O(nlogn)-space decision procedure for intuitionistic propositional logic, Journal of Logic and Computation, vol. 3 (1993), pp. 1–13, DOI: https://doi.org/10.1093/logcom/3.1.63
- D. Prawitz, Natural deduction: A proof-theoretical study, Almqvist & Wiksell (1965).
- R. Statman, Intuitionistic propositional logic is polynomial-space complete, Theoretical Computer Science, vol. 9 (1979), pp. 67–72, DOI: https://doi.org/10.1016/0304-3975(79)90006-9
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.