Во время тестирования свойств графов, алгоритм запрашивает целевой график на наличие или отсутствие ребер и потребностей , чтобы определить , либо имеет ли целевые определенное свойство или -far от того , свойства. (Алгоритм можно попросить преуспеть с 1-сторонней или 2-сторонней ошибкой.) Граф имеет -далее от того, чтобы иметь свойство, если никакие ребра могут быть добавлены / вычтены, чтобы сделать его иметь собственность.
Свойство называется тестируемым, если его можно протестировать указанным выше способом в сублинейном количестве запросов или, что еще лучше, в ряде запросов, не зависящих от (но не ). Понятие, что такое свойства, также может быть формализовано, но оно должно быть ясным.
Есть много результатов, характеризующих, какие свойства являются тестируемыми, и множество примеров естественных тестируемых свойств. Однако я не знаю многих естественных свойств, о которых известно, что они не поддаются тестированию (скажем, в постоянном количестве запросов), и мне знакомо это тестирование на изоморфизм данного графа.
Итак, мой вопрос: какие естественные свойства графа не проверяются?
Ответы:
В матричной модели смежности существует нижняя граница сложности запроса проверки, является ли nΩ ( n ) N состоит вершинный граф из двух изоморфных копий некоторого вершинного графа (см. Введение в тестирование свойств графа - Голдрайх для опрос).н / 2
Кроме того, есть много нижних границ, которые зависят от для тестеров с односторонней ошибкой, например: проверка ρN ρ клика, вырезки и ρ- деления (см. Тестирование свойства и его связь с обучением и приближением - Goldreich, Goldwasser, Рон )ρ ρ
Кроме того, в модели графа ограниченной степени для проверки 3-колорибельности требуется запросов, тогда как для тестирования 2-колорибельности (т. Е. Двудольности) требуется Ω ( √Ω ( n) (см.Проверка свойств в ограниченных графах степеней - Гольдрайх, Рон).Ω ( n--√)
источник