stringtranslate.com

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

Тестирование свойств — это область теоретической информатики , занимающаяся разработкой сверхбыстрых алгоритмов для приблизительного принятия решений, где решение относится к свойствам или параметрам огромных объектов. [1]

Алгоритм проверки свойств для задачи принятия решений — это алгоритм , сложность запроса которого (количество запросов, сделанных на его входе) намного меньше размера экземпляра задачи. Обычно алгоритмы проверки свойств используются для определения того, удовлетворяет ли некоторая комбинаторная структура S (например, граф или булева функция ) некоторому свойству P или «далека» от наличия этого свойства (это означает, что ε -доля представления S должна быть изменена, чтобы S удовлетворяла P ), используя лишь небольшое количество «локальных» запросов к объекту. [2] [3]

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

«Для данного графа с n вершинами определите, является ли он двудольным или его нельзя сделать двудольным даже после удаления произвольного подмножества из не более чем εn 2 ребер».

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

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

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

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

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

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

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

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

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

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

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

Для графа G с n вершинами понятие расстояния, которое мы будем использовать, — это расстояние редактирования . То есть, мы говорим, что расстояние между двумя графами — это наименьшее ε, такое, что можно добавить и/или удалить εn 2 ребер и перейти от первого графа ко второму. При разумном представлении графов это эквивалентно более раннему определению расстояния Хэмминга (с точностью до возможной замены констант).

Чтобы уточнить общие понятия тестирования свойств в контексте графов, мы говорим, что тестер для свойства графа P должен различать с вероятностью не менее ⅔ случаи, когда G удовлетворяет P , и случаи, когда G находится на ε -дальнем расстоянии редактирования от удовлетворения P. Тестер может получить доступ к некоторому оракулу , чтобы запросить, имеет ли пара вершин ребро между собой в G или нет. Сложность запроса - это количество таких запросов оракула. ​​Скажем, у тестера односторонняя ошибка , если у него есть ложные положительные результаты и нет ложных отрицательных, т. е. если G удовлетворяет P , тестер всегда выводит правильный ответ. [4] [5]

Мы можем различать только графы, удовлетворяющие P , и те, что далеки от P , в отличие от удовлетворяющих и не удовлетворяющих P. В последнем случае рассмотрим два графа: G, удовлетворяющий P, и H, не удовлетворяющий P , изменяя только несколько ребер. Одним из примеров является проверка отсутствия треугольников, когда H — граф с ровно одним треугольником, а G — с удаленным одним из этих ребер. Тогда тестер не сможет отличить их, если не запросит каждое ребро, чего он сделать не может.

Краткая история

Область тестирования свойств графа была впервые введена Голдрайхом, Голдвассером и Роном. В их основополагающей статье, опубликованной в 1998 году, анализируется абстрактная проблема разбиения графа и предоставляются некоторые тестеры. Они включают в себя в качестве особых случаев несколько важных свойств графа, таких как двудольность , k -раскрашиваемость , наличие большой клики и наличие большого разреза . [4] В частности, все естественные алгоритмы, которые выбирают подграф и проверяют, удовлетворяет ли он свойству, являются правильными, хотя и с, возможно, неоптимальной сложностью запроса.

С тех пор было сделано несколько связанных с этим открытий.

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

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

Теорема (Алон и Шапира 2008). Каждое наследственное свойство графа можно проверить с односторонней ошибкой. [2]

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

Теорема (лемма об удалении бесконечного графа). Для каждого (возможно бесконечного) множества графов H и ε > 0 существуют h 0 и δ > 0 , так что если G является n -вершинным графом с менее чем δn v ( H ) копиями H для каждого H ∈ H с не более чем h 0 вершинами, то G можно сделать индуцированно H -свободным путем добавления/удаления менее чем εn 2 ребер. [9]

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

Неформально, забывчивый тестер не замечает размер входных данных. Для свойства графа P это алгоритм, который принимает в качестве входных данных параметр ε и граф G , а затем запускается как алгоритм тестирования свойств на G для свойства P с параметром близости ε , который делает ровно q ( ε ) запросов к G.

Определение. Забывчивый тестер — это алгоритм, который принимает в качестве входных данных параметр ε . Он вычисляет целое число q ( ε ) , а затем запрашивает у оракула индуцированный подграф H на ровно q ( ε ) вершинах из G , выбранных равномерно случайным образом. Затем он принимает или отклоняет (возможно, случайным образом) в соответствии с ε и H . Мы говорим, что он проверяет свойство P, если он принимает с вероятностью не менее 2/3 для G , который имеет свойство P , и отклоняет с вероятностью не менее 2/3 для G , который ε -далек от наличия свойства P . [2] [1] [10]

Важно отметить, что количество запросов, которые делает забывчивый тестер, является константой, зависящей только от ε , а не от размера входного графа G. В полной аналогии с алгоритмами тестирования свойств можно говорить о забывчивых тестерах с односторонней ошибкой.

Тестирование свойств полунаследственного графа

Мы можем придумать некоторые свойства графа, для которых тестер должен иметь доступ к количеству вершин.

Пример. Граф G удовлетворяет свойству P, если он является двудольным с четным числом вершин или совершенным с нечетным числом вершин. [2]

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

Определение. Свойство графа H является полунаследственным , если существует наследственное свойство графа H такое, что любой граф, удовлетворяющий P, удовлетворяет H , и для каждого ε > 0 существует M ( ε ) такое, что любой граф размера не менее M ( ε ) , который ε -далек от удовлетворяющего P, содержит индуцированный подграф, который не удовлетворяет H. [2]

Тривиально, наследственные свойства также являются полунаследственными. Эта характеристика частично отвечает обратному к другой теореме Алона и Шапиры выше: свойства, которые легко проверить (имеющие забывчивых тестеров с односторонней ошибкой), являются почти наследственными. В той же статье они показали, что

Теорема (Алон и Шапира 2008). Графическое свойство P имеет забывчивый односторонний тестер ошибок тогда и только тогда, когда P является полунаследственным. [2]

Примеры: тестирование некоторых свойств графа

В этом разделе мы дадим несколько естественных забывающих алгоритмов тестирования с односторонней ошибкой для треугольников-свободы , двудольности и k -раскрашиваемости . Они естественны в том смысле, что мы следуем естественной идее случайной выборки некоторого подмножества X вершин G и проверки того, выполняется ли свойство графа на подграфе, охватываемом X, с помощью поиска методом перебора . У нас есть односторонняя ошибка, поскольку эти свойства на самом деле наследственные: если G удовлетворяет свойству, то и индуцированный подграф, охватываемый X , должен так же, поэтому наш тестер всегда принимает.

Для треугольнико-свободы тестер является применением леммы об удалении треугольников . В частности, он говорит нам, что если граф G ε -далек от того, чтобы быть треугольнико-свободным, то существует (вычислимая) константа δ = δ ( ε ), такая, что G имеет по крайней мере δn 3 треугольников.

Пример (Алгоритм проверки отсутствия треугольников).

  1. Дан граф G , выбираем случайный набор X из q ( ε ) = 1/ δ троек вершин независимо друг от друга случайным образом, где δ такое же, как указано выше.
  2. Для каждой тройки вершин в X спросите , являются ли все три пары вершин смежными в G.
  3. Алгоритм принимает решение , если ни одна тройка вершин не образует треугольник, и отклоняет его в противном случае. [1]

Для двудольности и k -раскрашиваемости пусть δ будет желаемой верхней границей вероятности ошибки для следующих тестеров. Обратите внимание, что сложность запроса не следует путать со временем выполнения. Последнее часто является экспоненциальным (как и в случае обоих) из-за отсутствия полиномиального алгоритма принятия решения для проверки свойства на индуцированном подграфе. Вместо этого мы проверяем методом грубой силы . [4]

Пример (алгоритм двухкомпонентного тестирования).

  1. Для данного графа G выберем случайное множество X из q ( ε ) = O (log(1/( εδ ))/ ε 2 ) вершин.
  2. Для каждой пары вершин в X спросите , являются ли они смежными в G.
  3. Он принимает , если индуцированный подграф G на X является двудольным, и отвергает в противном случае. [4]

Пример (алгоритм проверки k-раскрашиваемости).

  1. Дан граф G , выберем случайное множество X из q ( ε ) = O ( k4log2 ( k / δ ) / ε3 ) вершин .
  2. Для каждой пары вершин в X спросите , являются ли они смежными в G.
  3. Он принимает , если индуцированный подграф G на X является k-раскрашиваемым, и отвергает в противном случае. [4]

Ссылки

  1. ^ abc Goldreich, Oded (2017). Введение в тестирование свойств . Cambridge University Press. ISBN 9781107194052.
  2. ^ abcdefgh Алон, Нога ; Шапира, Асаф (2008). «Характеристика свойств (естественного) графа, проверяемых с односторонней ошибкой» (PDF) . SIAM Journal on Computing . 37 (6): 1703–1727. doi :10.1137/06064888X.
  3. ^ Goldreich, Oded (1999). "Комбинаторное тестирование свойств (обзор)". Методы рандомизации в разработке алгоритмов . Серия DIMACS по дискретной математике и теоретической информатике. 43 : 45–59. doi : 10.1090/dimacs/043/04 . ISBN 0821870874.
  4. ^ abcde Goldreich, Oded; Goldwasser, Shafi; Ron, Dana (1 июля 1998 г.). «Тестирование свойств и его связь с обучением и приближением». Journal of the ACM . 45 (4): 653–750. doi : 10.1145/285055.285060 .
  5. ^ Рубинфельд, Ронитт; Шапира, Асаф (2011). «Сублинейные временные алгоритмы». Журнал SIAM по дискретной математике . 25 (4): 1562–1588. CiteSeerX 10.1.1.221.1797 . doi :10.1137/100791075. S2CID  1319122. 
  6. ^ Алон, Н.; Дьюк, РА; Лефманн, Х.; Родл, В.; Юстер, Р. (1 января 1994 г.). «Алгоритмические аспекты леммы регулярности». Журнал алгоритмов . 16 (1): 80–109. doi :10.1006/jagm.1994.1005.
  7. ^ Алон, Нога; Фишер, Эльдар; Кривелевич, Михаил; Сегеди, Марио (1 апреля 2000 г.). «Эффективное тестирование больших графов». Комбинаторика . 20 (4): 451–476. дои : 10.1007/s004930070001.
  8. ^ Алон, Нога; Шапира, Асаф (22 мая 2005 г.). «Каждое свойство монотонного графа проверяемо». Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений . стр. 128–137. doi :10.1145/1060590.1060611. ISBN 1581139608. S2CID  14096855.
  9. ^ Фокс, Джейкоб (2010). «Новое доказательство леммы об удалении графа». arXiv : 1006.1300 [math.CO].
  10. ^ Рон, Дана (2000). Испытание свойств (технический отчет).