Počet záznamů: 1

On extracting computations from propositional proofs

SYSNO ASEP	0422140
Druh ASEP	C - Konferenční příspěvek (mezinárodní konf.)
Zařazení RIV	D - Článek ve sborníku
Název	On extracting computations from propositional proofs
Tvůrce(i)	Pudlák, Pavel (MU-W)_{RID, SAI}
Zdroj.dok.	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. - Wadem : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2010 / Lodaya K. ; Mahajan M - ISBN 978-3-939897-23-1
Rozsah stran	s. 30-41
Poč.str.	12 s.
Forma vydání	Tištěná - P
Akce	International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), /30./
Datum konání	15.12.2010-16.12.2010
Místo konání	Chennai
Země	IN - Indie
Typ akce	WRD
Jazyk dok.	eng - angličtina
Země vyd.	DE - Německo
Klíč. slova	proof complexity ; propositional tautology ; boolean circuits
Vědní obor RIV	BA - Obecná matematika
CEP	IAA100190902 GA AV ČR - Akademie věd
	1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy
CEZ	AV0Z10190503 - MU-W (2005-2011)
UT WOS	000310361000003
EID SCOPUS	84880199880
DOI	10.4230/LIPIcs.FSTTCS.2010.30
Anotace	This paper describes a project that aims at showing that propositional proofs of certain tautologies in weak proof system give upper bounds on the computational complexity of functions associated with the tautologies. Such bounds can potentially be used to prove (conditional or unconditional) lower bounds on the lengths of proofs of these tautologies and show separations of some weak proof systems. The prototype are the results showing the feasible interpolation property for resolution. In order to prove similar results for systems stronger than resolution one needs to define suitable generalizations of boolean circuits. We will survey the known results concerning this project and sketch in which direction we want to generalize them.
Pracoviště	Matematický ústav
Kontakt	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Rok sběru	2014

Počet záznamů: 1