Approximate counting by hashing in bounded arithmetic

0326451 - MÚ 2010 RIV US eng J - Článek v odborném periodiku
Jeřábek, Emil
Approximate counting by hashing in bounded arithmetic.
[Aproximativní počítání pomocí hashování v omezené aritmetice.]
Journal of Symbolic Logic. Roč. 74, č. 3 (2009), s. 829-860. ISSN 0022-4812. E-ISSN 1943-5886
Grant CEP: GA AV ČR IAA1019401
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: bounded arithmetic * approximate counting * universal hashing
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.631, rok: 2009

We show how to formalize approximate counting via hash functions in subsystems of bounded arithmetic, using variants of the weak pigeonhole principle. We discuss several appications, including a proof of the tournament principle, and an improvement on the known relationship of the collapse of the bounded arithmetic hierarchy tot he collapse of the polynomial-time hierarchy.

Ukážeme, jak zformalizovat aproximativní počítání pomocí hashovacích funkcí v podsystémech omezené aritmetiky s použitím slabého principu PHP. Uvádíme několik aplikací, včetně důkazu turnajového principu a vylepšení známé souvislosti kolapsu hierarchie omezených aritmetik s kolapsem polynomiální hierarchie.
Trvalý link: http://hdl.handle.net/11104/0173553