Dolní odhady pro obvody pomocí her Ehrenfeucht a Fraisse

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F06%3A00041325" target="_blank" >RIV/67985840:_____/06:00041325 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games
Popis výsledku v původním jazyce
In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC0 circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC0 circuits.
Název v anglickém jazyce
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games
Popis výsledku anglicky
In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC0 circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC0 circuits.

Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2006
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku
Proceedings of 21st Annual IEEE Conference on Computational Complexity
ISBN
0-7695-2596-2
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
190-201
Název nakladatele
IEE Computer Society Press
Místo vydání
New York
Místo konání akce
Praha
Datum konání akce
16. 7. 2006
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)