Alternating minima and maxima, Nash equilibria and bounded arithmetic

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F12%3A00374023" target="_blank" >RIV/67985840:_____/12:00374023 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.apal.2011.06.014" target="_blank" >http://dx.doi.org/10.1016/j.apal.2011.06.014</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.apal.2011.06.014" target="_blank" >10.1016/j.apal.2011.06.014</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Alternating minima and maxima, Nash equilibria and bounded arithmetic

Popis výsledku v původním jazyce

We show that the least number principle for (strict ) formulas can be characterized by the existence of alternating minima and maxima of length k. We show simple prenex forms of these formulas whose herbrandizations (by polynomial time functions) are formulas that characterize theorems of the levels of the Bounded Arithmetic Hierarchy, and we derive from this another characterization, in terms of a search problem about finding pure Nash equilibria in k-turn games.

Název v anglickém jazyce

Alternating minima and maxima, Nash equilibria and bounded arithmetic

Popis výsledku anglicky

We show that the least number principle for (strict ) formulas can be characterized by the existence of alternating minima and maxima of length k. We show simple prenex forms of these formulas whose herbrandizations (by polynomial time functions) are formulas that characterize theorems of the levels of the Bounded Arithmetic Hierarchy, and we derive from this another characterization, in terms of a search problem about finding pure Nash equilibria in k-turn games.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/IAA100190902" target="_blank" >IAA100190902: Matematická logika, složitost a algoritmy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2012

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 periodika

Annals of Pure and Applied Logic

ISSN

0168-0072

e-ISSN

—

Svazek periodika

163

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

11

Strana od-do

604-614

Kód UT WoS článku

000301211700010

EID výsledku v databázi Scopus

—