Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Есептеу күрделілігі теориясында, ықтималдықпен тексерілетін дәлелдеме (PCP) – бұл кездейсоқ алгоритм арқылы, шектелген мөлшерде кездейсоқтық қолданылып және дәлелдеменің шектелген саны биті оқылған кезде тексерілетін дәлелдеме түрі. Алгоритм дұрыс дәлелдемелерді қабылдауға, ал дұрыс емес дәлелдемелерді өте жоғары ықтималдықпен қабылдамауға тиіс. NP күрделілік класының тексерушіге негізделген анықтамасындағы стандартты дәлелдеме (немесе сертификат) да осы талаптарға жауап береді, себебі тексеру процедурасы детерминистік түрде дәлелдеменің барлық бөлігін оқиды, әрқашан дұрыс дәлелдемелерді қабылдайды және дұрыс емес дәлелдемелерді қабылдамайды. Бірақ, оларды ерекше ететіні – дәлелдеменің тек бірнеше битін оқып, кездейсоқтықты маңызды рөлде пайдаланатын ықтималдықпен тексерілетін дәлелдемелердің болуы. Ықтималдықпен тексерілетін дәлелдемелер, қажетті сұранымдар санына және қолданылатын кездейсоқтық мөлшеріне байланысты көптеген күрделілік сыныптарын тудырады. PCP[r(n),q(n)] класы – бұл полиномиялық уақытта, ең көп дегенде r(n) кездейсоқ бит және ең көп дегенде q(n) бит оқылып тексерілетін ықтималдықпен тексерілетін дәлелдемелері бар шешім проблемаларының жиынтығын білдіреді. Басқаша көрсетілмесе, дұрыс дәлелдемелер әрқашан қабылдануы керек, ал дұрыс емес дәлелдемелер 1/2-ден жоғары ықтималдықпен қабылдамауы керек. Компьютерлік күрделілік теориясының маңызды нәтижесі болып табылатын PCP теоремасы, PCP[O(log n),O(1)] = NP екенін көрсетеді.
In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate), as used in the verifier based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way. Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The class PCP[r(n),q(n)] refers to the set of decision problems that have probabilistically checkable proofs that can be verified in polynomial time using at most r(n) random bits and by reading at most q(n) bits of the proof. Unless specified otherwise, correct proofs should always be accepted, and incorrect proofs should be rejected with probability greater than 1/2. The PCP theorem, a major result in computational complexity theory, states that PCP[O(log n),O(1)] = NP.
Тарих және маңызы
Ықтималдықпен тексерілетін дәлелдемелер теориясы параметрлердің әртүрлі шектеулері (толықтығы, дұрыстығы, кездейсоқтық күрделілігі, сұраныс күрделілігі және әліпби мөлшері) бойынша ықтималдықпен тексерілетін дәлелдеме жүйелерінің мүмкіндіктерін зерттейді. Оның есептеу күрделілігі (әсіресе, жуықтаудың қиындығы) және криптография салаларында қолданылуы бар. Ықтималдықпен тексерілетін дәлелдеме туралы анықтаманы 1992 жылы Арора мен Сафра енгізді, бірақ оның қасиеттері одан бұрын зерттелген. 1990 жылы Бабаи, Фортноу және Лунд PCP[poly(n), poly(n)] = NEXP екенін дәлелдеді, бұл стандартты дәлелдемелер (NEXP) мен ықтималдықпен тексерілетін дәлелдемелер арасындағы алғашқы маңызды теңдестік болды. 1992 жылы дәлелденген PCP теоремасы PCP[O(log n),O(1)] = NP деп мәлімдейді. Жуықтаудың қиындығы теориясы ықтималдықпен тексерілетін дәлелдемелерде толықтық, дұрыстық, әліпби мөлшері және сұраныс күрделілігінің рөлін толық түсінуді қажет етеді.
The theory of probabilistically checkable proofs studies the power of probabilistically checkable proof systems under various restrictions of the parameters (completeness, soundness, randomness complexity, query complexity, and alphabet size). It has applications to computational complexity (in particular hardness of approximation) and cryptography. The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992, although their properties were studied earlier. In 1990 Babai, Fortnow, and Lund proved that PCP[poly(n), poly(n)] = NEXP, providing the first nontrivial equivalence between standard proofs (NEXP) and probabilistically checkable proofs. The PCP theorem proved in 1992 states that PCP[O(log n),O(1)] = NP. The theory of hardness of approximation requires a detailed understanding of the role of completeness, soundness, alphabet size, and query complexity in probabilistically checkable proofs.
Сызықтық ПТК
Сызықтық PCP – бұл дәлелдемесі шекті өрістің элементтерінен құралған вектор болып табылатын және PCP оракулына дәлелдемеге қатысты тек сызықтық операциялар жасауға рұқсат берілетін PCP. Яғни, тексеруші сұранысына оракулдың жауабы – сызықтық функция. Сызықтық PCP-лер SNARK-ке компиляцияланатын дәлелдеу жүйелерінде маңызды қолданысқа ие.
A Linear PCP is a PCP in which the proof is a vector of elements of a finite field , and such that the PCP oracle is only allowed to do linear operations on the proof. Namely, the response from the oracle to a verifier query is a linear function Linear PCPs have important applications in proof systems that can be compiled into SNARKs.