Výsledky vyhledávání

Report

On proof theory in computational complexity: overview

In [GH1] and [GH2] (see also [GH3]) we presented full proof of the equalities NP = coNP = PSPACE. These results have been obtained by the novel proof theoretic tree-to-dag compressing techniques adapted to Prawitz's Natural Deduction (ND) for proposi

Externí odkaz: http://arxiv.org/abs/2201.04118

Zobrazit plný text záznamu

Report

On proof theory in computer science

Autor: Gordeev, L., Haeusler, E. H.

The subject logic in computer science should entail proof theoretic applications. So the question arises whether open problems in computational complexity can be solved by advanced proof theoretic techniques. In particular, consider the complexity cl

Externí odkaz: http://arxiv.org/abs/2012.04437

Zobrazit plný text záznamu

Report

Proof Compression and NP Versus PSPACE II: Addendum

Autor: Gordeev, L., Haeusler, E. H.

Publikováno v: Bulletin of the Section of Logic (51), 9 pp. (2022)

In [3] we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier's cut-free sequent calculus for minimal logic (HSC) [5] with the horizontal compressing in the corresponding minimal Prawitz-style natural deduct

Externí odkaz: http://arxiv.org/abs/2011.09262

Zobrazit plný text záznamu

Report

PUC-Logic

Autor: Fernandes, R. Q. A, Haeusler, E. H., Pereira, L. C. P. D

We present a logic for Proximity-based Understanding of Conditionals (PUC-Logic) that unifies the Counterfactual and Deontic logics proposed by David Lewis. We also propose a natural deduction system (PUC-ND) associated to this new logic. This infere

Externí odkaz: http://arxiv.org/abs/1402.1535

Zobrazit plný text záznamu