Tractability of cut-free Gentzen type propositional calculus with permutation inference
type: Item
instance of: scholarly article
title: Tractability of cut-free Gentzen type propositional calculus with permutation inference
zbMATH Open document ID: 0874.03065
DOI: 10.1016/S0304-3975(96)80704-3
author: Noriko H. Arai
published in: Theoretical Computer Science
publication date: 1997-02-27T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 984748
zbMATH Keywords: automatic reasoning
zbMATH Keywords: computational complexity
zbMATH Keywords: permutation
zbMATH Keywords: cut-free Gentzen type propositional calculus
zbMATH Keywords: polynomial size proofs for hard combinatorial problems
zbMATH Keywords: pigeonhole principles
zbMATH Keywords: consistency
zbMATH Keywords: subformula property
zbMATH Keywords: relative efficiency
zbMATH Keywords: Frege systems
MaRDI profile type: Publication
cites work: The complexity of the pigeonhole principle
cites work: Tractability through symmetries in propositional calculus
cites work: Polynomial size proofs of the propositional pigeonhole principle
cites work: Propositional consistency proofs
cites work: Q3794177
cites work: Q3140635
cites work: The relative efficiency of propositional proof systems
cites work: Q4133141
cites work: The intractability of resolution
cites work: Q5593816
cites work: The complexity of Gentzen systems for propositional logic
cites work: Hard examples for resolution
full work available at URL: s0304-3975(96)80704-3
OpenAlex ID: W4252046485
description: scientific article; zbMATH DE number 984748