The polynomial and linear time hierarchies in V-0

Kód výsledku v IS VaVaI

RIV/67985840:_____/09:00337059 - isvavai.cz

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

The polynomial and linear time hierarchies in V-0

Popis výsledku v původním jazyce

We show that the bounded arithmetic theory V-0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). The result follows from a lower bound for bounded depth circuits computing prefix parity, wherethe circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai.

Název v anglickém jazyce

The polynomial and linear time hierarchies in V-0

Popis výsledku anglicky

We show that the bounded arithmetic theory V-0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). The result follows from a lower bound for bounded depth circuits computing prefix parity, wherethe circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai.

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

LC505: Centrum Eduarda Čecha pro algebru a geometrii

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2009

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

Mathematical Logic Quarterly

ISSN

0942-5616

e-ISSN

—

Svazek periodika

55

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

6

Strana od-do

—

Kód UT WoS článku

000270961200004

EID výsledku v databázi Scopus

—