Гипотеза Аандераа — Карпа — Розенберга

Нерешённые проблемы информатики: Доказать или опровергнуть гипотезу Аандераа — Карпа — Розенберга.

Гипотеза Аандераа — Карпа — Розенберга (известная также как гипотеза Аандераа — Розенберга или гипотеза трудности) — это группа связанных гипотез о числе вопросов в форме «Имеется ли ребро меду вершиной u и вершиной v?», на которые следует ответить, чтобы определить, обладает или нет неориентированный граф определённым свойством (инвариантом), таким как планарность или двудольность. Гипотеза названа именами норвежского математика Стола Аандераа и американских учёных Ричарда М. Карпа и Арнольда Л. Розенберга. Согласно гипотезе, для широкого класса инвариантов никакой алгоритм не может гарантировать, что алгоритм может опустить какой-либо запрос — любой алгоритм определения, обладает ли граф свойством, неважно, насколько умён этот алгоритм, он должен проверить каждую пару вершин, прежде чем дать ответ. Свойство, удовлетворяющее гипотезе, называется трудным.

Более точно, гипотеза Аандераа — Розенберга утверждает, что любой детерминированный алгоритм должен проверить по меньшей мере фиксированную долю всех возможных пар вершин, чтобы определить в худшем случае любое нетривиальное монотонное свойство графа. В этом контексте свойство монотонно, если оно остаётся верным при добавлении рёбер (так что свойство планарности монотонным не является, а вот непланарность монотонна). Более строгая версия этой гипотезы, называемая гипотезой трудности или гипотезой Аандераа — Карпа — Розенберга, утверждает, что необходимо в точности ${\tfrac {n(n-1)}{2}}$ проверок. Были сформулированы и изучались версии проблемы для вероятностных и квантовых алгоритмов.

Детерминированную гипотезу Аандераа — Розенберга доказали Ривест и Виллемин, но более сильная гипотеза гипотеза Аандераа — Карпа — Розенберга остаётся недоказанной. Кроме того, существует большая разница между нижней границей и лучшей доказанной нижней границей для вероятностной и квантовой сложности по количеству запросов.

Пример

Свойство не быть пустым (то есть, иметь по меньшей мере одно ребро) монотонно, поскольку добавление другого ребра к непустому графу даёт непустой граф. Существует простой алгоритм тестирования, является ли граф не пустым — цикл через все пары вершин и проверка, связана ли каждая пара ребром. Если ребро найдено таким способом, прерываем цикл и рапортуем, что граф не пустой, а если цикл завершается без нахождения какого-либо ребра, то рапортуем, что граф пустой. На таких графах (например, полных графах) этот алгоритм быстро завершается без проверки каждой пары вершин, но на пустом графе алгоритм проверяет все возможные пары перед тем как завершиться. Поэтому, сложность алгоритма по запросам равна ${\tfrac {n(n-1)}{2}}$ — в худшем случае алгоритм делает${\tfrac {n(n-1)}{2}}$ проверок.

Описанный выше алгоритм не является единственным возможным методом проверки непустоты, но из гипотезы Аандераа — Карпа — Розенберга вытекает, что любой детерминантный алгоритм для проверки непустоты имеет ту же сложность по запросам ${\tfrac {n(n-1)}{2}}$. То есть свойство быть непустым является трудным. Для этого свойства результат просто проверить прямо — если алгоритм не выполнит ${\tfrac {n(n-1)}{2}}$ проверок, он не сможет отличить пустой граф от графа, содержащего одно ребро непроверенной пары вершин и должен дать неверный ответ для одного из двух этих графов (либо для пустого, либо для графа с ребром).

Определения

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

Неформально, свойство графа (или инвариант графа, оба термина в данной статье используются как синонимы) — это свойство графа, которое не зависит от разметки. Более формально, свойство графа — это отображение из множества всех графов в {0,1} так что изоморфные графы отображаются в одно и то же значение. Например, свойство содержать по меньшей мере одну вершину степени 2 является инвариантом графа, но свойство, что первая вершина имеет степень 2 инвариантом графа не является, поскольку свойство зависит от разметки графа (в частности, оно зависит от того, какая вершина считается «первой»). Инвариант графа называется нетривиальным, если он не имеет одно и то же значение для всех графов. Например, свойство быть графом является тривиальным свойством, поскольку все графы этим свойством обладают. Но с другой стороны, свойство быть пустым нетривиально, поскольку пустой граф обладает данным свойством, а непустой не обладает. Говорят, что свойство графа монотонно, если добавление рёбер не разрушает свойства. Альтернативно, если граф обладает монотонным свойством, тогда любой суперграф этого графа на том же наборе вершин тоже обладает этим свойством. Например, свойство быть непланарным монотонно — суперграф непланарного графа также непланарен. Однако, свойство быть регулярным не монотонно.

Для сложности запросов часто используется нотация «O» большое. Кратко, f(n) есть $O(g(n))$, если для любого достаточно большого $nf(n)\leqslant cg(n)$ для некоторой положительной константы c. Аналогично, f(n) есть $\Omega (g(n))$, если для достаточно больших $nf(n)\geqslant cg(n)$ для некоторой положительной константы c. Наконец, f(n) есть $\Theta (g(n))$, если она есть как $O(g(n))$, так и $\Omega (g(n))$.

Сложность запроса

Сложность детерминированного запроса вычисления функции от n бит $(x_{1},x_{2},\dots ,x_{n})$ равна числу бит x_i, которые должен прочитать детерминированный алгоритм в худшем случае для определения значения функции. Например, если функция принимает значение 0, если все биты равны 0 и значение 1 в противном случае (то есть функция OR), то сложность детерминированных запросов в точности равна n. В худшем случае первые n − 1 прочитанных бит будут равны 0 и значение функции будет зависеть только от последнего бита. Если алгоритм не прочитает этот бит, он может дать неверный ответ. Число прочитанных бит называется также числом запросов, сделанных на входе. Можно представить так, что алгоритм спрашивает (осуществляет запрос) вход о конкретном бите и вход отвечает на этот запрос.

Сложность вероятностного запроса выполнения функции определяется аналогично, за исключением того, что алгоритм может быть вероятностным, то есть он может подбрасывать монету и использовать выпавшее значение стороны монеты для решения, какой бит запрашивать. Однако, вероятностный алгоритм должен продолжать давать верные ответы на все входные запросы — ошибки недопустимы. Такие алгоритмы называются алгоритмами Лас-Вегаса и их следует отличать от алгоритмов Монте-Карло, в которых некоторые ошибки допустимы. Сложность вероятностного запроса может быть определена в смысле Монте-Карло, но гипотеза Аандераа — Карпа — Розенберга говорит о сложности запросов для инвариантов графа в смысле Лас-Вегаса.

Квантовая сложность запросов является естественным обобщением сложности вероятностного запроса, естественно, с разрешением квантовых запросов и ответов. Квантовая сложность запросов может быть также определена в смысле алгоритмов Монте-Карло или алгоритмов Лас-Вегаса, но обычно имеются ввиду квантовые алгоритмы Монте-Карло.

В контексте этой гипотезы вычисляемая функция является свойством графа, а входом является строка размера ${\tfrac {n(n-1)}{2}}$, которая задаёт местоположение рёбер на графе с n вершинами, поскольку граф может иметь максимум ${\tfrac {n(n-1)}{2}}$ рёбер. Сложность запроса любой функции ограничена сверху значением ${\tfrac {n(n-1)}{2}}$, поскольку весь вход будет прочитан после ${\tfrac {n(n-1)}{2}}$ запросов, что и определяет полностью входной граф.

Сложность детерминированных запросов

Для детерминированных алгоритмов Розенберг предположил, что для всех нетривиальных свойств графов на n вершинах решение, обладает ли граф этим свойством, требует $\Omega (n^{2})$ запросов. Ясно, что требуется нетривиальность условия, поскольку существуют тривиальные свойства типа «это граф?», на которые можно ответить без всякого запроса вообще.

Граф-скорпион. Одна из трёх красных вершин смежна всем вешинам, не принадлежащим этому пути, остальные же две вершины пути смежны только вершинам пути.

Гипотезу опроверг Аандераа, который предложил свойство ориентированного графа (свойство иметь «сток»), проверка которого требует всего O(n) запросов. Сток в ориентированном графе — это вершина, имеющая входящую полустепень n-1 и исходящую полустепень 0. Это свойство может быть проверено за менее чем 3n запросов. Свойство неориентированного графа, которое может быть проверено за O(n) запросов, это свойство «граф является графом-скорпионом», впервые описанное в статье Беста, ван Эмде Боаза и Ленстры. Граф «скорпион» — это граф, содержащий путь, состоящий из трёх вершин, такой что одна конечная вершина пути соединена со всеми остальными вершинами графа, в то время как две оставшиеся вершины пути соединены только с вершинами самого пути.

Тогда Аандераа и Розенберг сформулировали новую гипотезу (гипотезу Аандераа — Розенберга), которая утверждает, что решение, обладает ли граф нетривиальным монотонным свойством, требует $\Omega (n^{2})$ запросов. Эту гипотезу решили Райвест и Вюйемен, показав, что нужно по меньшей мере ${\tfrac {n^{2}}{16}}$ запросов для проверки любого нетривиального монотонного свойства. Границу позже улучшили до ${\tfrac {n^{2}}{9}}$ Клейтман и Квятковски, затем до ${\tfrac {n^{2}}{4}}-o(n^{2})$ Кан, Сакс и Стертевант, до ${\tfrac {8}{25}}n^{2}-o(n^{2})$ Корнефель и Триш и до ${\tfrac {n^{2}}{3}}-o(n^{2})$ Шайдервайлер и Триш.

Ричард Карп высказал более строгое утверждение (которое называется теперь гипотезой о трудности или гипотезой Аандераа–Карпа–Розенберга), что «любое нетривиальное монотонное свойство графов на n вершинах трудное» . Свойство называется трудным, если определение, обладает ли граф данным свойством, требует ${\tfrac {n(n-1)}{2}}$ запросов. Эта гипотеза утверждает, что лучший алгоритм тестирования любого нетривиального монотонного свойства должно (в худшем случае) запросить все возможные рёбра. Эта гипотеза остаётся открытой, хотя было показано, что некоторые специальные свойства графов являются трудным для всех n. Гипотеза была решена для случая, когда n является степенью простого числа Каном, Саксом и Стертевантом с помощью топологического подхода. Гипотезу решил для всех нетривиальных монотонных свойств двудольных графов Яо. Было также доказано, что замкнутые относительно миноров свойства также трудны для больших n.

Сложность вероятностного запроса

Ричард Карп также высказал гипотезу, что $\Omega (n^{2})$ запросов требуется для проверки нетривиальных свойств монотонности даже если вероятностные алгоритмы разрешены. Никакого нетривиального свойства не известно, которое требует менее ${\tfrac {n^{2}}{4}}$ запросов для проверки. Линейная нижняя граница (то есть, $\Omega (n))$ для всех монотонных свойств следует из очень общей связи между вероятностными и детерминированными сложностями запросов. Первую суперлинейную нижнюю для всех монотонных инвариантов дал Яо, показавший, что требуется $\Omega (n\log ^{\tfrac {1}{12}}n)$ запросов. Её затем улучшил Кинг до $\Omega (n^{\tfrac {5}{4}})$, а затем Хайналь до $\Omega (n^{\tfrac {4}{3}})$. Этот результат затем улучшили до текущего хорошо известного значения границы $\Omega (n^{\tfrac {4}{3}}\log ^{\tfrac {1}{3}}n)$ Чакрабарти и Хот.

Некоторые последние результаты дают нижние границы, которые определяются критической вероятностью p монотонного свойства рассматриваемого графа. Критическая вероятность p определяется как единственное p, такое что случайный граф G(n, p) обладает этим свойством с вероятностью 1/2. Случайный граф G(n, p) — это граф с n вершинами, в котором каждое ребро присутствует с вероятностью p и наличие/отсутствие ребра не зависит от всех остальных рёбер. Фридгуд, Кан и Вигдерсон показали, что любой монотонный инвариант графа с критической вероятностью p требует $\Omega \left(\min \left\{{\frac {n}{\min(p,1-p)}},{\frac {n^{2}}{\log n}}\right\}\right)$ запросов. Для той же проблемы О'Доннелл, Сакс, Шрамм и Серведио показали нижнуюю границу $\Omega ({\frac {n^{\tfrac {4}{3}}}{p^{\tfrac {1}{3}}}})$.

Как в детерминированном случае, есть много специальных инвариантов, для которых нижняя граница $\Omega (n^{2})$ известна. Более того, известны лучшие границы для некоторых классов инвариантов графов. Например, для проверки, имеет ли граф подграф, изоморфный какому-нибудь заданному графу (так называемая задача поиска изоморфного подграфа), лучшей известной нижней границей, согласно Грёгеру, является $\Omega (n^{\tfrac {3}{2}})$.

Квантовая сложность запросов

Для равномерно ограниченной ошибки квантовой сложности запросов наилучшая известная нижняя граница равна $\Omega (n^{\tfrac {2}{3}}\log ^{\tfrac {1}{6}}n)$, как заметил Эндрю Яо. Граница получена комбинированием вероятностной нижней границы с квантовым состязательным методом (англ. quantum adversary method). Наилучшая нижняя граница, которую надеются достичь, равна $\Omega (n)$, в отличие о классического случая, ввиду алгоритма Гровера, который даёт алгоритм с O(n) запросами для проверки монотонного свойства непустоты. Аналогично детерминированному и вероятностному случаям, есть некоторые свойства, которые, как известно, имеют нижнюю границу $\Omega (n)$, например непустота (что следует из оптимальности алгоритма Гровера) и свойство содержать тругольник. Есть некоторые инварианты графа, для которых известно, что они имеют нижнюю границу $\Omega (n^{\tfrac {3}{2}})$, и даже есть свойства с нижней границей $\Omega (n^{2})$. Например, монотонное свойство непланарности требует $\Theta (n{\tfrac {3}{2}})$ запросов, а монотонное свойства содержать более половины возможных рёбер (которое называется также мажоритарной функцией) требует $\Theta (n^{2})$ запросов.

Литература для дальнейшего чтения

• Béla Bollobás. Chapter VIII. Complexity and packing // Extremal Graph Theory. — New York: Dover Publications, 2004. — С. 401–437. — ISBN 978-0-486-43596-1.
• László Lovász; Young, Neal E. "Lecture Notes on Evasiveness of Graph Properties". arXiv:cs/0205031v1. {{cite arXiv}}: Неизвестный параметр |год= игнорируется (справка)
• Catherine E Chronaki. A survey of Evasiveness: Lower Bounds on the Decision-Tree Complexity of Boolean Functions. — 1990.
• Michael Saks. Decision Trees: Problems and Results, Old and New  (неопр.).