Тестирование собственности - Property testing

В Информатика, а проверка собственности алгоритм для проблема решения является алгоритм чей сложность запроса к его входу намного меньше, чем размер экземпляра проблемы. Обычно алгоритмы проверки свойств используются для определения того, является ли какой-либо математический объект (например, график или логическая функция ) имеет «глобальное» свойство или «далек» от этого свойства, используя лишь небольшое количество «локальных» запросов к объекту.

Например, следующие проблема обещания допускает алгоритм, сложность запроса которого не зависит от размера экземпляра (для произвольной константы ε> 0):

"Учитывая график грамм на п вершины, решите, если грамм является двудольный, или же грамм нельзя сделать двудольным даже после удаления произвольного подмножества не более

{ displaystyle epsilon { tbinom {п} {2}}}

края грамм."

Алгоритмы проверки собственности имеют центральное значение для определения вероятностно проверяемые доказательства, поскольку вероятностно проверяемое доказательство, по сути, является доказательством, которое может быть проверено алгоритмом проверки свойств.

Определение и варианты

Формально алгоритм проверки собственности со сложностью запроса q(п) и параметр близости ε для задачи решения L это рандомизированный алгоритм что на входе Икс (экземпляр L) составляет не более q(|Икс|) запросы к Икс и ведет себя следующим образом:

Если Икс в L, алгоритм принимает Икс с вероятностью не менее.
Если Икс ε-далеко от L, алгоритм отклоняет Икс с вероятностью не менее.

Здесь, "Икс ε-далеко от L"означает, что расстояние Хэмминга между Икс и любая строка в L не меньше ε |Икс|.

Говорят, что алгоритм проверки свойств имеет односторонняя ошибка если он удовлетворяет более сильному условию, что вероятность принятия для экземпляров x ∈ L равно 1 вместо ⅔.

Алгоритм проверки свойств называется неадаптивный если он выполняет все свои запросы до того, как «наблюдает» какие-либо ответы на предыдущие запросы. Такой алгоритм можно рассматривать как работающий следующим образом. Сначала алгоритм получает входные данные. Перед просмотром ввода, используя его внутреннюю случайность, алгоритм решает, какие символы ввода следует запросить. Далее алгоритм наблюдает за этими символами. Наконец, без каких-либо дополнительных запросов (но, возможно, с использованием его случайности), алгоритм решает, принять или отклонить ввод.

Особенности и ограничения

Основным параметром эффективности алгоритма проверки свойств является сложность его запроса, которая представляет собой максимальное количество входных символов, проверяемых на всех входах заданной длины (и всех случайных выборах, сделанных алгоритмом). Один интересуется разработкой алгоритмов, сложность запросов которых минимальна. Во многих случаях время работы алгоритмов проверки свойств составляет сублинейный в длине экземпляра. Обычно цель состоит в том, чтобы сделать запрос как можно меньшей сложностью в зависимости от размера экземпляра. п, а затем изучите зависимость от параметра близости ε.

В отличие от других теоретико-сложных настроек, на асимптотическую сложность запросов алгоритмов тестирования свойств существенно влияет представление экземпляров. Например, при ε = 0,01 задача проверки двудольности плотные графы (которые представлены их матрицей смежности) допускают алгоритм постоянной сложности запроса. Напротив, разреженные графики на п вершины (которые представлены их списком смежности) требуют алгоритмов проверки свойств сложности запроса ${ displaystyle Omega ({ sqrt {n}})}$ .

Сложность запроса алгоритмов проверки свойств растет по мере того, как параметр близости ε становится меньше для всех нетривиальных свойств. Эта зависимость от ε необходима, поскольку изменение менее чем ε символов во входных данных не может быть обнаружено с постоянной вероятностью, используя менее O (1 / ε) запросов. Многие интересные свойства плотных графов можно проверить, используя сложность запроса, которая зависит только от ε, а не от размера графа. п. Однако сложность запроса может чрезвычайно быстро расти в зависимости от ε. Например, давно известный алгоритм проверки того, не работает ли график. содержать любой треугольник была сложность запроса, которая функция башни из поли(1 / ε), и только в 2010 году она была улучшена до башенной функции бревно(1 / ε). Одна из причин такого огромного роста оценок заключается в том, что многие положительные результаты тестирования свойств графов устанавливаются с использованием Лемма Семереди о регулярности, который также имеет в своих выводах границы башенного типа. Связь проверки свойств с леммой Семереди о регулярности и связанными с ней леммами об удалении графов подробно рассматривается ниже.

Тестирование свойств графиков

Для графиков с п вершин, мы будем использовать понятие расстояния - это расстояние редактирования. То есть мы говорим, что расстояние между двумя графами - это наименьшее ε, такое, что можно добавлять и / или удалять ${ Displaystyle varepsilon п ^ {2}}$ рёбер и перейти от первого графа ко второму. При разумном представлении графов это эквивалентно более раннему определению расстояния Хэмминга (с возможной заменой констант). Для графиков существует характеристика того, какие свойства легко проверить. А именно, свойства, которые легко проверить, - это в точности те свойства, которые являются (почти) наследственными. Эти заявления будут разъяснены ниже. Прежде всего, под тем, что свойство легко проверить, мы имеем в виду, что у него есть невнимательный тестер.

Невнимательные тестировщики

Неофициально невнимательный тестировщик для свойства графа п - алгоритм, который принимает на вход параметр ε и график грамм, а затем запускается как алгоритм проверки свойств на грамм для собственности п с параметром близости ε, который составляет ровно q(ε) запросы к грамм. Важно отметить, что количество запросов, которые делает не обращающий внимания тестировщик, постоянно зависит только от ε. Формальное определение состоит в том, что тестировщик, не обращающий внимания на это, - это алгоритм, который принимает на вход параметр ε. Он вычисляет целое число q(ε), а затем запрашивает у оракула индуцированный подграф ЧАС точно на q(ε) вершин из грамм выбирается равномерно случайным образом. Затем он принимает или отклоняет в соответствии с ε и ЧАС. Как и раньше, мы говорим, что это проверка на свойство п если он принимает с вероятностью не менее для грамм у которого есть собственность п, и отклоняет с вероятностью не менее или грамм то есть ε-далек от свойства п. В полной аналогии с алгоритмами тестирования свойств, мы можем говорить о не обращающих внимания тестерах с односторонней ошибкой.

Проверка наследственных свойств

А наследственная собственность - свойство, которое сохраняется при удалении вершин. Несколько важных наследственных свойств: ЧАС-свободность (для некоторого графика ЧАС), k-крашиваемость, и плоскостность. Все наследственные свойства поддаются проверке, и есть доказательство этого факта с использованием версии лемма об удалении графа для бесконечных семейств индуцированных подграфов. На самом деле, можно сказать и об обратном: свойства, у которых есть не обращающие внимания тестеры с односторонней ошибкой, являются почти наследственными (Alon & Shapira 2008), в некотором смысле, который здесь не будет уточняться.

Пример: проверка свободы от треугольников

В этом разделе мы сделаем набросок доказательства существования не обращающего внимания тестера на отсутствие треугольников; это доказательство является применением лемма об удалении треугольника.

Эскиз доказательства: Если график грамм ε-далеко не без треугольников, то по лемме об удалении треугольников существует (вычислимая) константа ${ Displaystyle дельта = дельта ( varepsilon)}$ так что грамм имеет по крайней мере ${ displaystyle delta n ^ {3}}$ треугольники. Не обращая внимания на образцы тестера ${ Displaystyle д ( varepsilon) = 1 / дельта}$ тройки вершин независимо от графа случайным образом. Он принимает, если никакая тройка вершин не индуцирует треугольник, и отклоняет в противном случае.

Если грамм не содержит треугольников, то очевидно, что этот алгоритм всегда принимает.
Если грамм ε-далеко не без треугольников, то более чем ${ displaystyle 6 / delta}$ доля троек вершин в грамм создать треугольник, и тогда нетрудно увидеть, что вероятность того, что алгоритм найдет хотя бы один треугольник, больше.

Следовательно, приведенный выше алгоритм - это не обращающий внимания тестер с односторонней ошибкой на отсутствие треугольников.