Počet záznamů: 1

On the complexity of circuit satisfiability

  1. 1.
    0351120 - MU-W 2011 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
    Paturi, R. - Pudlák, Pavel
    On the complexity of circuit satisfiability.
    STOC'10 : Proceedings of the 2010 ACM International Symposium on Theory of Computing. New York: Association for Computing Machinery, 2010, s. 241-249. ISBN 978-1-60558-817-9.
    [Symposium on Theory of Computing : STOC'10. Cambridge (US), 05.06.2010-08.06.2010]
    Grant CEP: GA MŠk(CZ) 1M0545; GA AV ČR IAA100190902
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: Circuit satisfiability * NP-completeness
    Kód oboru RIV: BA - Obecná matematika
    http://dl.acm.org/citation.cfm?doid=1806689.1806724

    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.
    Trvalý link: http://hdl.handle.net/11104/0190940
    Název souboruStaženoVelikostKomentářVerzePřístup
    Pudlak4.pdf6167.3 KBAutorský postprintpovolen