Počet záznamů: 1
Logical Strength of Complexity Theory and a Formalization of the PCP Theorem in Bounded Arithmetic
- 1.0507203 - ÚI 2020 DE eng J - Článek v odborném periodiku
Pich, Ján
Logical Strength of Complexity Theory and a Formalization of the PCP Theorem in Bounded Arithmetic.
Logical Methods in Computer Science. Roč. 11, č. 2 (2015), č. článku 8. ISSN 1860-5974. E-ISSN 1860-5974
Klíčová slova: weak pigeonhole principle * provability * hardness * np * Bounded arithmetic * Complexity theory * Formalizations
Impakt faktor: 0.569, rok: 2015
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.
Trvalý link: http://hdl.handle.net/11104/0298247
Počet záznamů: 1