Bachelor's thesis

PCP theorem

Andrea Večerková
Abstract

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 …more

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 …more

Keywords
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
Thesis description
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.
Administrative information
The thesis has been checked:
14/5/2026 08:52, Mgr. Jan Grebík, Ph.D.
Full text of thesis
881,1 KB / file PDF
Language used
English English
Defence date
25/6/2026
The thesis was defended successfully

Supervisor

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

Reader

doc. Mgr. Michal Kunc, Ph.D., UČO 2906
ÚMS Ústavy PřF MU

Consultant

doc. Lukáš Vokřínek, PhD., UČO 43588
ÚMS Ústavy PřF MU
Cite this text
Masaryk University Faculty of Science
Programme
Plan
Mathematics

Theses on a related topic

List of theses with an identical keyword.

  • 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.