Number of the records: 1

On the complexity of circuit satisfiability

SYSNO ASEP	0351120
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	On the complexity of circuit satisfiability
Author(s)	Paturi, R. (US) Pudlák, Pavel (MU-W)_{RID, SAI}
Source Title	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
Pages	s. 241-249
Number of pages	9 s.
Action	Symposium on Theory of Computing : STOC'10
Event date	05.06.2010-08.06.2010
VEvent location	Cambridge
Country	US - United States
Event type	WRD
Language	eng - English
Country	US - United States
Keywords	Circuit satisfiability ; NP-completeness
Subject RIV	BA - General Mathematics
R&D Projects	1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
	IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
CEZ	AV0Z10190503 - MU-W (2005-2011)
EID SCOPUS	77954691768
DOI	10.1145/1806689.1806724
Annotation	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.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2011

Number of the records: 1