A note on Jerabek's paper "A simplified lower bound for implicational logic"
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908860384542720 |
|---|---|
| author | Gordeev, Lev Haeusler, Edward Hermann |
| author_facet | Gordeev, Lev Haeusler, Edward Hermann |
| contents | In our previous papers we sketched proofs of the equality NP = coNP = PSPACE. These results have been obtained by proof theoretic tree-to-dag compressing techniques adapted to Prawitz's Natural Deduction (ND) for implicational minimal logic with references to Hudelmaier's cutfree sequent calculus. In this note we comment on Jeřábek's approach that claimed to refute our results by providing exponential lower bounds on the implicational minimal logic. This claim is wrong and misleading, which is briefly demonstrated by Basis example below. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_01929 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A note on Jerabek's paper "A simplified lower bound for implicational logic" Gordeev, Lev Haeusler, Edward Hermann Computational Complexity In our previous papers we sketched proofs of the equality NP = coNP = PSPACE. These results have been obtained by proof theoretic tree-to-dag compressing techniques adapted to Prawitz's Natural Deduction (ND) for implicational minimal logic with references to Hudelmaier's cutfree sequent calculus. In this note we comment on Jeřábek's approach that claimed to refute our results by providing exponential lower bounds on the implicational minimal logic. This claim is wrong and misleading, which is briefly demonstrated by Basis example below. |
| title | A note on Jerabek's paper "A simplified lower bound for implicational logic" |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2603.01929 |