У теорији рачунске сложености, проверљиви докази помоћу вероватноће (ПЦП, ) представљају врсту математичких доказа које је могуће проверити случајним (вероватносним) алгоритмом користећи ограничену количину случајности и прочитавши ограничен број битова самог доказа. Од овог алгоритма захтева се да са врло великом вероватноћом прихвати исправне доказе, односно одбаци неисправне доказе. Стандардан доказ, односно сертификат, као што се користи у дефиницији класе сложености NP заснованој на верификатору, такође испуњава ове услове, будући да процедура провере детерминистички чита цео доказ, увек прихвата исправне доказе и одбацује неисправне. Међутим, оно што је посебно значајно код проверљивих доказа помоћу вероватноће јесте постојање таквих доказа који се могу проверити читањем само неколико битова доказа, користећи случајност на суштински начин.

Проверљиви докази помоћу вероватноће доводе до многих класа сложености у зависности од броја потребних упита и количине коришћене случајности. Класа се односи на скуп проблема одлучивања који имају проверљиве доказе помоћу вероватноће који се могу верификовати у полиномијалном времену користећи највише r(n) случајних битова и читањем највише q(n) битова доказа. Осим ако није другачије назначено, исправни докази би увек требало да буду прихваћени, а неисправни докази одбачени са вероватноћом већом од 1/2. ПЦП теорема, главни резултат у теорији рачунске сложености, тврди да је .

Дефиниција За дати проблем одлучивања L (или језик L са својим алфабетом Σ), систем проверљивих доказа помоћу вероватноће за L са потпуношћу c(n) и исправношћу s(n), где је , састоји се од доказивача и верификатора. За дато тврђено решење x дужине n, које може бити нетачно, доказивач производи доказ π који наводи да x решава (, доказ је ниска ). Верификатор је рандомизована Тјурингова машина са оракулом V (верификатор) која проверава доказ π за тврдњу да x решава (или ) и одлучује да ли да прихвати тврдњу. Систем има следећа својства: Потпуност: За свако , с обзиром на доказ π који је произвео доказивач система, верификатор прихвата тврдњу са вероватноћом од најмање c(n), Исправност: За свако , онда за било који доказ π, верификатор грешком прихвата тврдњу са вероватноћом од највише s(n).

За рачунску сложеност верификатора, верификатор је полиномијалног времена, а имамо сложеност случајности r(n) за мерење максималног броја случајних битова које V користи над свим x дужине n и сложеност упита q(n) верификатора је максималан број упита које V упућује ка π над свим x дужине n.

У горњој дефиницији, дужина доказа се не помиње јер обично укључује скуп алфабета и све сведоке. За доказивача, не занима нас како долази до решења проблема; занима нас само доказ који даје о припадности решења језику.

Каже се да је верификатор неадаптиван ако постави све своје упите пре него што прими било који од одговора на претходне упите.

Класа сложености је класа свих проблема одлучивања који имају системе проверљивих доказа помоћу вероватноће над бинарним алфабетом са потпуношћу c(n) и исправношћу s(n), где је верификатор неадаптиван, извршава се у полиномијалном времену, и има сложеност случајности r(n) и сложеност упита q(n).

Скраћена нотација се понекад користи за . Класа сложености ПЦП је дефинисана као .

Историја и значај Теорија проверљивих доказа помоћу вероватноће проучава моћ система проверљивих доказа помоћу вероватноће под различитим ограничењима параметара (потпуност, исправност, сложеност случајности, сложеност упита и величина алфабета). Има примене у рачунској сложености (посебно тежина апроксимације) и криптографији.

Дефиницију проверљивих доказа помоћу вероватноће експлицитно су увели Арора и Сафра 1992. године, иако су њена својства проучавана и раније. Године 1990, Бабаи, Фортнау и Лунд су доказали да је PCP[poly(n), poly(n)] = NEXP, пружајући прву нетривијалну еквиваленцију између стандардних доказа (NEXP) и проверљивих доказа помоћу вероватноће. ПЦП теорема доказана 1992. године тврди да је .

Теорија тежине апроксимације захтева детаљно разумевање улоге потпуности, исправности, величине алфабета и сложености упита у проверљивим доказима помоћу вероватноће.

Својства Са становишта рачунске сложености, за екстремна подешавања параметара, дефиниција проверљивих доказа помоћу вероватноће се лако може видети као еквивалентна стандардним класама сложености. На пример, имамо следеће за различита подешавања : ( је дефинисано тако да нема случајности и нема приступ доказу.) (Логаритамски број случајних битова не помаже Тјуринговој машини полиномијалног времена, јер би могла да испроба све могуће случајне ниске логаритамске дужине у полиномијалном времену.) (Без случајности, доказ се може сматрати фиксном ниском логаритамске величине. Машина полиномијалног времена би могла да испроба све могуће доказе логаритамске величине и случајне ниске константне дужине у полиномијалном времену.) (По дефиницији coRP.) (По дефиницији NP заснованој на верификатору.)

ПЦП теорема и MIP = NEXP могу се окарактерисати на следећи начин: (ПЦП теорема) . +Табела једнакости00PPPNPPPPNPPNPNPNPcoRPMIP = NEXPNEXPNEXP Такође је познато да је . Посебно, . С друге стране, ако је онда је P = NP.

Линеарни ПЦП Линеарни ПЦП је ПЦП у којем је доказ вектор елемената коначног поља , и такав да је ПЦП оракулу дозвољено само да врши линеарне операције над доказом. Наиме, одговор оракула на упит верификатора је линеарна функција . Линеарни ПЦП-ови имају важне примене у системима доказивања који се могу компајлирати у СНАРК-ове (, од — сажети неинтерактивни аргументи знања).

Референце

Спољашње везе Холографски доказ у Енциклопедији математике Белешке са курса о ПЦП аутора Субаша Хота са Универзитета у Њујорку, 2008. Белешке са курса о ПЦП и Историја ПЦП теореме аутора Рајана О'Донела и Венкатесана Гурусвамија са Универзитета у Вашингтону, 2005.

Категорија:Математички докази Категорија:Рандомизовани алгоритми