Тестирование собственности

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

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

«Учитывая график G на п вершинах, решить , если G является двудольным или G не может быть сделан двудольным даже после удаления произвольного подмножества в большинстве ребер G » .

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

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

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

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

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

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

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

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

Возможности и ограничения [ править ]

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

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

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

Тестирование свойств графиков [ править ]

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

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

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

Проверка наследственных свойств [ править ]

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

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

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

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

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

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

Ссылки [ править ]

Гольдрайх, Одед (2017). Введение в тестирование собственности . Издательство Кембриджского университета. ISBN 9781107194052. CS1 maint: обескураженный параметр ( ссылка )
Рон, Дана (2000). Тестирование собственности (Технический отчет). CS1 maint: обескураженный параметр ( ссылка )
Рубинфельд, Ронитт; Шапира, Асаф (2011). «Сублинейные временные алгоритмы». Журнал СИАМ по дискретной математике . 25 (4): 1562–1588. CiteSeerX 10.1.1.221.1797 . DOI : 10.1137 / 100791075 .
Гольдрайх, Одед (1999). «Тестирование комбинаторных свойств (обзор)» . Методы рандомизации в разработке алгоритмов . 43 : 45–59. ISBN 0821870874. CS1 maint: обескураженный параметр ( ссылка )
Фокс, Джейкоб (2010). «Новое доказательство леммы об удалении графа». arXiv : 1006.1300 .
Алон, Нога ; Шапира, Асаф (2008). «Характеристика (естественных) свойств графа, проверяемых с односторонней ошибкой» (PDF) . SIAM Journal on Computing . 37 : 1703–1727. CS1 maint: обескураженный параметр ( ссылка )