Počet záznamů: 1

On the complexity of circuit satisfiability

SYSNO ASEP	0351120
Druh ASEP	C - Konferenční příspěvek (mezinárodní konf.)
Zařazení RIV	D - Článek ve sborníku
Název	On the complexity of circuit satisfiability
Tvůrce(i)	Paturi, R. (US) Pudlák, Pavel (MU-W)_{RID, SAI}
Zdroj.dok.	STOC'10 : Proceedings of the 2010 ACM International Symposium on Theory of Computing. - New York : Association for Computing Machinery, 2010 - ISBN 978-1-60558-817-9
Rozsah stran	s. 241-249
Poč.str.	9 s.
Akce	Symposium on Theory of Computing : STOC'10
Datum konání	05.06.2010-08.06.2010
Místo konání	Cambridge
Země	US - Spojené státy americké
Typ akce	WRD
Jazyk dok.	eng - angličtina
Země vyd.	US - Spojené státy americké
Klíč. slova	Circuit satisfiability ; NP-completeness
Vědní obor RIV	BA - Obecná matematika
CEP	1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy
	IAA100190902 GA AV ČR - Akademie věd
CEZ	AV0Z10190503 - MU-W (2005-2011)
EID SCOPUS	77954691768
DOI	10.1145/1806689.1806724
Anotace	We derive tight bounds on the exponent of the success probability for deciding the circuit satisfiability problem in a variety of probabilistic computational models under complexity asumptions.
Pracoviště	Matematický ústav
Kontakt	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Rok sběru	2011

Počet záznamů: 1