Abstracts Mathematics

PCP-teoreeman todistaminen: Proving the PCP theorem

by Valtteri Nyman

Tässä tutkielmassa esitellään lyhyesti PCP-teoreema, minkä jälkeen tutkielmassa pala palalta käydään läpi teoreeman todistamiseen tarvittavia työkaluja. Tutkielman lopussa todistetaan PCP-teoreema. Vaativuusluokka PCP[O(log n), O(1)] sisältää ne ongelmat, joilla on olemassa todistus, josta vakio määrän bittejä lukien probabilistinen Turingin kone kykenee ratkaisemaan ongelman käyttäen samalla vain logaritmisen määrän satunnaisuutta suhteessa syötteen kokoon. PCP-teoreema väittää vaativuusluokan NP kuuluvan vaativuusluokkaan PCP[O(log n), O(1)]. Väritys on funktio, joka yhdistää kuhunkin joukon muuttujaan jonkin symbolin. Rajoite joillekin muuttujille on lista symboleista, joita rajoite sallii asetettavan muuttujille. Jos väritys asettaa muuttujille vain rajoitteen sallimia symboleja, rajoite on tyytyväinen väritykseen. Optimointi-ongelmat koskevat sellaisten väritysten etsimistä, että mahdollisimman moni rajoite joukosta rajoitteita on tyytyväinen väritykseen. PCP-teoreemalla on yhteys optimointi-ongelmiin, ja tätä yhteyttä hyödyntäen tutkielmassa todistetaan PCP-teoreema. Tutkielma seuraa I. Dinurin vastaavaa todistusta vuoden 2007 artikkelista The PCP Theorem by Gap Amplification. Rajoiteverkko on verkko, jonka kuhunkin kaareen liittyy jokin rajoite. Rajoiteverkkoon liittyy lisäksi aakkosto, joka sisältää ne symbolit, joita voi esiintyä verkon rajoitteissa ja värityksissä. Tutkielman päälauseen avulla kyetään kasvattamaan rajoiteverkossa olevien värityksiin tyytymättömien rajoitteiden suhteellista osuutta. Päälause takaa, että verkon koko säilyy samassa kokoluokassa, ja että verkon aakkoston koko ei muutu. Lisäksi jos verkon kaikki rajoitteet ovat tyytyväisiä johonkin väritykseen, päälauseen tuottaman verkon kaikki rajoitteet ovat edelleen tyytyväisiä johonkin väritykseen. Päälause koostetaan kolmessa vaiheessa, joita kutakin vastaa tutkielmassa yksi osio. Näistä ensimmäisessä, tutkielman osiossa 4, verkon rakenteesta muovataan sovelias seuraavia osioita varten. Toisessa vaiheessa, jota vastaa osio 6, verkon kävelyitä hyödyntäen kasvatetaan tyytymättömien rajoitteiden lukumäärää, mutta samalla verkon aakkosto kasvaa. Kolmannessa vaiheessa, osiossa 5, aakkoston koko saadaan pudotettua kolmeen sopivan algoritmin avulla. Osiossa 7 kootaan päälause ja todistetaan lausetta toistaen PCP-teoreema.