|
Персональные инструменты |
![]() |
||
|
![]() |
![]() PCP — различия между версиямиМатериал из CustisWiki
Версия 07:40, 7 декабря 2005Пусть , неотрицательные целочисленные функции. Класс сложности состоит из языков, имеющих верифицирующую PCP-систему, которая на входе x :
Класс PCP для множеств целочисленных функций R, Q, определяется следующим образом:
Поэтому, например, PCP(log,1) означает класс языков, верифицируемых PCP-системой, потребляющей случайных бит и константу (не обязательно единицу!) ответов от оракула. В том случае, когда определение класса зависит от точного числа запросов к оракулу, применяют обозначения вида PCP(log,q=3),PCP(log,q=3) и т.п.
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «PCP» |
![]() |
||
![]() |
![]() |