LOGICAL STRENGTH OF COMPLEXITY THEORY AND A FORMALIZATION OF THE PCP THEOREM IN BOUNDED ARITHMETIC

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10317967" target="_blank" >RIV/00216208:11320/15:10317967 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

LOGICAL STRENGTH OF COMPLEXITY THEORY AND A FORMALIZATION OF THE PCP THEOREM IN BOUNDED ARITHMETIC

Popis výsledku v původním jazyce

We present several known formalizations of theorems from computational complexity in bounded arithmetic and formalize the PCP theorem in the theory PV1 (no formalization of this theorem was known). This includes a formalization of the existence and of some properties of the (n, d, lambda)-graphs in PV1.

Název v anglickém jazyce

LOGICAL STRENGTH OF COMPLEXITY THEORY AND A FORMALIZATION OF THE PCP THEOREM IN BOUNDED ARITHMETIC

Popis výsledku anglicky

We present several known formalizations of theorems from computational complexity in bounded arithmetic and formalize the PCP theorem in the theory PV1 (no formalization of this theorem was known). This includes a formalization of the existence and of some properties of the (n, d, lambda)-graphs in PV1.

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Svazek periodika

11

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

6

Strana od-do

—

Kód UT WoS článku

000359470700005

EID výsledku v databázi Scopus

2-s2.0-84938322119