Bakalářská práce

PCP theorem

Andrea Večerková
Anotace

Tato práce se zabývá PCP větou (větou o pravděpodobnostně ověřitelných důkazech), která patří mezi základní výsledky teorie složitosti. PCP věta dává novou charakterizaci třídy NP. Hlavním cílem práce je představit nový kombinatorický důkaz PCP věty od Irit Dinur, založený na její inaproximabilitní formulaci. Na začátku práce tuto formulaci uvedeme a dokážeme její ekvivalenci s klasickým zněním PCP …více

Abstract

This thesis studies the PCP (Probabilistically Checkable Proofs) theorem, a fundamental result in complexity theory that provides a new characterization of the class NP. The main focus of the thesis is Dinur’s combinatorial proof of the PCP theorem through the inapproximability formulation. At the beginning of the thesis, we will present the inapproximability version of the PCP theorem and demonstrate …více

Klíčová slova
pravděpodobnostně ověřitelné důkazy obtížnost aproximace expandery problémy s omezujícími podmínkami zvětšování meze nesplnitelnosti probabilistically checkable proofs hardness of approximation expander graphs constraint satisfaction problems gap amplification
Zadání práce
Cílem bakalářské práce je porozumět novému důkazu PCP věty od Irit Dinur. PCP věta patří mezi klíčové výsledky v teorii složitosti. Nový důkaz má kombinatorický charakter a využívá teorii grafových expanderů – jeden z konceptů, který propojuje různé oblasti matematiky a teoretické informatiky. Součástí práce bude seznámení se základy teorie expanderů a může obsahovat také přehled různých aplikací tohoto významného výsledku.
Administrativní informace
Práce zkontrolována:
14. 5. 2026 08:52, Mgr. Jan Grebík, Ph.D.
Plný text práce
881,1 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
25. 6. 2026
Práce byla úspěšně obhájena

Vedoucí

Mgr. Jan Grebík, Ph.D.
ÚMS Ústavy PřF MU

Oponent

doc. Mgr. Michal Kunc, Ph.D., učo 2906
ÚMS Ústavy PřF MU

Konzultant

doc. Lukáš Vokřínek, PhD., učo 43588
ÚMS Ústavy PřF MU
Citovat tuto práci
Masarykova univerzita Přírodovědecká fakulta
Studijní program
Plán
Obecná matematika

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.