Substitutions into propositional tautologies
type: Item
instance of: scholarly article
title: Substitutions into propositional tautologies
zbMATH Open document ID: 1185.68629
author: Jan Krajíček
published in: Information Processing Letters
publication date: 2010-01-29T00:00:00Z
Mathematics Subject Classification ID: 68T15
zbMATH DE Number: 5664752
zbMATH Keywords: computational complexity
zbMATH Keywords: proof complexity
zbMATH Keywords: automated theorem proving
MaRDI profile type: Publication
full work available at URL: j.ipl.2006.09.002
OpenAlex ID: W2052661699
cites work: Pseudorandom Generators in Propositional Proof Complexity
cites work: Q5715680
cites work: The relative efficiency of propositional proof systems
cites work: A Computing Procedure for Quantification Theory
cites work: A machine program for theorem-proving
cites work: On the weak pigeonhole principle
cites work: Tautologies from pseudo-random generators
cites work: Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
cites work: Diagonalization in proof complexity
cites work: Q5718678
cites work: Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
cites work: Natural proofs
DOI: 10.1016/J.IPL.2006.09.002
Recommended article: SUBSTITUTION IN RELEVANT LOGICS
Recommended article: Logic of proofs with substitution
Recommended article: Propositions and the substitution anomaly
Recommended article: Theories of propositional logics and the converse of substitution
Recommended article: Q4375805
Recommended article: Theories of the classical propositional logic and substitutions
Recommended article: Substitution and Propositional Proof Complexity
Recommended article: Axiomatisation of substitution
description: scientific article; zbMATH DE number 5664752