Complexity of subclasses of the intuitionistic propositional calculus
type: Item
instance of: scholarly article
title: Complexity of subclasses of the intuitionistic propositional calculus
zbMATH Open document ID: 0790.03041
DOI: 10.1007/BF01995108
published in: BIT
publication date: 1994-06-22T00:00:00Z
review text: The author investigates the complexity of the decision problem for subclasses of intuitionistic propositional calculus (IPC) determined by syntactic restrictions, and presents upper bounds for decision procedures locating these subclasses into a lower complexity class like co-NP or polynomial time. His subclasses of IPC are defined in terms of the normal form \(X\Rightarrow g\), where \(g\) is a propositional variable and \(X\) is a list of the formulas of the form \(^ \sim p\), \(p\), \((p\Rightarrow q)\), \(p\Rightarrow(q\Rightarrow r)\), \((p\Rightarrow q)\Rightarrow r\), \(p\Rightarrow(q\lor r)\), \(p\Rightarrow ^ \sim q\), \(^ \sim q\Rightarrow p\), where \(p\), \(q\), \(r\) are variables.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03B20
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 438468
zbMATH Keywords: complexity of the decision problem for subclasses of intuitionistic propositional calculus
zbMATH Keywords: upper bounds for decision procedures
author: G. E. Mints
reviewed by: M.Tetruashvili
MaRDI profile type: Publication
cites work: Q5812175
cites work: Q3972527
cites work: Justification of the structural synthesis of programs
cites work: Q3999860
cites work: Q5604436
full work available at URL: https://doi.org/10.1007/bf01995108
OpenAlex ID: W1978593318
Recommended article: Proof complexity of substructural logics
Recommended article: Q4934563
Recommended article: Proof complexity of intuitionistic implicational formulas
Recommended article: Complexity of intuitionistic propositional logic and its fragments
Recommended article: On the complexity of propositional quantification in intuitionistic logic
Recommended article: Proof theoretic complexity of low subrecursive classes
Recommended article: Q5013887
Recommended article: Q3505074
Recommended article: The Computational Complexity of Propositional Cirquent Calculus
Recommended article: Complexity of deductions in a system of classical propositional calculus
description: scientific article; zbMATH DE number 438468