Введение
Концепция в информатике
В теории сложности ZPP (zero error probabilistic polynomial time) — это класс сложности задач, для которых существует вероятностная машина Тьюринга, обладающая следующими свойствами:
Она всегда возвращает правильный ответ «ДА» или «НЕТ». Время работы полиномиально в среднем для любого входного набора данных. Иными словами, если алгоритму разрешено использовать истинно случайную монету во время работы, он всегда будет возвращать правильный ответ, и для задачи размера n существует некоторый полином p(n), такой что среднее время работы будет меньше, чем p(n), хотя в отдельных случаях оно может быть значительно больше. Такой алгоритм называется алгоритмом Лас-Вегаса. Альтернативно, ZPP можно определить как класс задач, для которых существует вероятностная машина Тьюринга, обладающая следующими свойствами:
Она всегда работает за полиномиальное время. Она возвращает ответ «ДА», «НЕТ» или «НЕ ИЗВЕСТНО». Ответ всегда либо «НЕ ИЗВЕСТНО», либо правильный ответ. Она возвращает «НЕ ИЗВЕСТНО» с вероятностью не более 1/2 для любого входного набора данных (и правильный ответ в противном случае). Оба определения эквивалентны. Определение ZPP основано на вероятностных машинах Тьюринга, но для ясности следует отметить, что другие классы сложности, основанные на них, включают BPP и RP. Класс BQP основан на другой машине, использующей случайность: квантовом компьютере.
It always runs in polynomial time. It returns an answer YES, NO or DO NOT KNOW. The answer is always either DO NOT KNOW or the correct answer. It returns DO NOT KNOW with probability at most 1/2 for every input (and the correct answer otherwise). The two definitions are equivalent. The definition of ZPP is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer.
Определение пересечения
Класс ZPP точно равен пересечению классов RP и co RP. Это часто принимается за определение ZPP. Чтобы показать это, сначала заметим, что для каждой задачи, которая находится как в RP, так и в co RP, существует алгоритм Лас-Вегаса следующим образом:
Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co RP algorithm B. Given an input, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. If it returns NO, the answer must be NO. If neither occurs, repeat this step. Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the kth round shrinks exponentially in k, showing that the expected running time is polynomial. This shows that RP intersect co RP is contained in ZPP. To show that ZPP is contained in RP intersect co RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm:
Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO. By Markov's Inequality, the chance that it will yield an answer before we stop it is at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an RP algorithm. The co RP algorithm is identical, except that it gives YES if C "times out".
Предположим, у нас есть язык L, распознаваемый как алгоритмом RP A, так и (возможно, совершенно другим) алгоритмом co RP B. Получив входные данные, выполните алгоритм A на этих данных один шаг. Если он возвращает ДА, то ответ должен быть ДА. В противном случае выполните алгоритм B на этих данных один шаг. Если он возвращает НЕТ, то ответ должен быть НЕТ. Если ни один из этих случаев не произошел, повторите этот шаг. Обратите внимание, что только одна машина может дать неверный ответ, и вероятность того, что эта машина даст неверный ответ при каждом повторении, не превышает 50%. Это означает, что вероятность достижения k-го раунда экспоненциально уменьшается с ростом k, что показывает, что ожидаемое время работы полиномиально. Это доказывает, что RP ∩ co RP содержится в ZPP. Чтобы показать, что ZPP содержится в RP ∩ co RP, предположим, что у нас есть алгоритм Лас-Вегаса C для решения задачи. Тогда мы можем построить следующий алгоритм RP:
Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co RP algorithm B. Given an input, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. If it returns NO, the answer must be NO. If neither occurs, repeat this step. Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the kth round shrinks exponentially in k, showing that the expected running time is polynomial. This shows that RP intersect co RP is contained in ZPP. To show that ZPP is contained in RP intersect co RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm:
Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO. By Markov's Inequality, the chance that it will yield an answer before we stop it is at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an RP algorithm. The co RP algorithm is identical, except that it gives YES if C "times out".
Запустите алгоритм C как минимум в два раза дольше его ожидаемого времени работы. Если он выдает ответ, выдайте этот ответ. Если он не выдает никакого ответа до того, как мы его остановим, выдайте НЕТ. По неравенству Маркова, вероятность того, что он выдаст ответ до того, как мы его остановим, составляет не менее 1/2. Это означает, что вероятность того, что мы дадим неверный ответ на экземпляре ДА, остановившись и выдав НЕТ, не превышает 1/2, что соответствует определению алгоритма RP. Алгоритм co RP идентичен, за исключением того, что он выдает ДА, если алгоритм C "превышает лимит времени".
Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co RP algorithm B. Given an input, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. If it returns NO, the answer must be NO. If neither occurs, repeat this step. Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the kth round shrinks exponentially in k, showing that the expected running time is polynomial. This shows that RP intersect co RP is contained in ZPP. To show that ZPP is contained in RP intersect co RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm:
Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO. By Markov's Inequality, the chance that it will yield an answer before we stop it is at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an RP algorithm. The co RP algorithm is identical, except that it gives YES if C "times out".
Теоретические свойства сложности
Известно, что ZPP замкнут относительно дополнения; то есть ZPP = co ZPP. ZPP является низким для себя, что означает, что машина ZPP, обладающая возможностью мгновенного решения задач ZPP (ZPP-оракул), не превосходит по мощности машину без этой дополнительной возможности. В символах, ZPPZPP = ZPP. ZPPNPBPP = ZPPNP. NPBPP содержится в ZPPNP.
Связь с другими классами
Поскольку ZPP = RP ∩ coRP, ZPP очевидно содержится как в RP, так и в coRP. Класс P содержится в ZPP, и некоторые ученые в области информатики предполагают, что P = ZPP, то есть каждый алгоритм Лас-Вегаса имеет детерминированный эквивалент с полиномиальной временной сложностью. Существует оракул, относительно которого ZPP = EXPTIME. Доказательство равенства ZPP и EXPTIME означало бы, что P ≠ ZPP, поскольку P ≠ EXPTIME (см. теорему об иерархии времени).