Гипотеза Андераа – Карпа – Розенберга - Aanderaa–Karp–Rosenberg conjecture

Нерешенная проблема в информатике: Докажите или опровергните гипотезу Андераа – Карпа – Розенберга. (больше нерешенных проблем в информатике)

В теоретическая информатика, то Гипотеза Андераа – Карпа – Розенберга (также известный как Гипотеза Андераа – Розенберга или догадка об уклончивости) - группа связанных догадки о количестве вопросов формы "Есть ли ребро между вершиной ты и вершина v? ", на которые нужно ответить, чтобы определить, неориентированный граф имеет особое свойство, такое как плоскостность или двудольность. Они названы в честь Stål Aanderaa, Ричард М. Карп, и Арнольд Л. Розенберг. Согласно гипотезе, для широкого класса свойств ни один алгоритм не может гарантировать, что он сможет пропустить любые вопросы: любые алгоритм для определения того, обладает ли граф этим свойством, каким бы умным он ни был, может потребоваться изучить каждую пару вершин, прежде чем он сможет дать свой ответ. Свойство, удовлетворяющее этой гипотезе, называется уклончивый.

Точнее, гипотеза Андераа – Розенберга утверждает, что любое детерминированный алгоритм должен проверять хотя бы постоянную долю всех возможных пар вершин в худший случай, для определения любого нетривиального свойства монотонного графа; в этом контексте свойство является монотонным, если оно остается истинным при добавлении ребер (таким образом, планарность не является монотонной, а непланарность монотонной). Более сильная версия этой гипотезы, называемая гипотезой об уклончивости или гипотезой Андераа – Карпа – Розенберга, утверждает, что именно п(п − 1)/2 нужны тесты. Версии задачи для рандомизированные алгоритмы и квантовые алгоритмы также были сформулированы и изучены.

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

пример

Свойство быть непустым (то есть иметь хотя бы одно ребро) является монотонным, потому что добавление еще одного ребра к непустому графу дает еще один непустой граф. Существует простой алгоритм проверки того, является ли граф непустым: перебрать все пары вершин, проверяя, соединена ли каждая пара ребром. Если ребро когда-либо было обнаружено таким образом, выйдите из цикла и сообщите, что граф не пуст, а если цикл завершится, не обнаружив никаких ребер, сообщите, что граф пуст. На некоторых графиках (например, полные графики ) этот алгоритм завершится быстро, без проверки каждой пары вершин, но на пустой график он проверяет все возможные пары перед завершением. Следовательно, сложность запроса этого алгоритма равна п(п - 1) / 2: в худшем случае алгоритм выполняет п(п - 1) / 2 теста.

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

Определения

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

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

В нотация большой O часто используется для определения сложности запроса. Короче, ж(п) равно O (грамм(п)) если для достаточно больших п, ж(п) ≤ c g(п) для некоторой положительной постоянной c. Так же, ж(п) есть Ω (грамм(п)) если для достаточно больших п, ж(п) ≥ c g(п) для некоторой положительной постоянной c. В заключение, ж(п) равно Θ (грамм(п)), если это одновременно O (грамм(п)) и Ω (грамм(п)).

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

Детерминированная сложность запроса для оценки функции на п биты (Икс₁, Икс₂, ..., Икс_п) - количество бит Икс_я которые должны быть прочитаны в худшем случае детерминированным алгоритмом для определения значения функции. Например, если функция принимает значение 0, когда все биты равны 0, и принимает значение 1 в противном случае (это ИЛИ ЖЕ функция), то детерминированная сложность запроса в точности равна п. В худшем случае первый п − 1 прочитанные биты могут быть 0, а значение функции теперь зависит от последнего бита. Если алгоритм не читает этот бит, он может выдать неверный ответ. (Такие аргументы называются противоборствующими аргументами.) Число прочитанных битов также называется числом запросов, сделанных ко входу. Можно представить, что алгоритм запрашивает (или запрашивает) вход для определенного бита, а входные данные отвечают на этот запрос.

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

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

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

Детерминированная сложность запроса

Для детерминированных алгоритмов Розенберг (1973) первоначально предположил, что для всех нетривиальных свойств графа на п вершин, чтобы решить, обладает ли граф этим свойством, требуется Ω (п²) запросы. Очевидно, что условие нетривиальности требуется, потому что есть тривиальные свойства вроде "это граф?" на который можно ответить без каких-либо вопросов.

График скорпиона. Одна из трех вершин красного пути смежна со всеми остальными вершинами, а две другие красные вершины не имеют других смежностей.

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

Затем Андераа и Розенберг сформулировали новую гипотезу ( Гипотеза Андераа – Розенберга), в котором говорится, что для определения того, обладает ли граф нетривиальным свойством монотонности графа, требуется Ω (п²) запросы.^[1] Эта гипотеза была разрешена Ривест и Вюйлемен (1975) показывая, что по крайней мере п²/ 16 запросов необходимы для проверки любого нетривиального свойства монотонного графа. Граница была дополнительно улучшена до п²/ 9 - пользователем Клейтман и Квятковски (1980), затем к п²/ 4 - o (п²) к Кан, Сакс и Стертевант (1983), затем до (8/25)п² - о (п²) к Корнеффель и Триеш (2010), а затем в п²/ 3 - o (п²) к Шайдвайлер и Триеш (2013).

Ричард Карп предположил более сильное утверждение (которое теперь называется догадка об уклончивости или Гипотеза Андераа – Карпа – Розенберга), что «каждое нетривиальное свойство монотонного графа для графов на п вершины уклончивы. "^[2] Недвижимость называется уклончивый если определение того, обладает ли данный граф этим свойством, иногда требует всех п(п - 1) / 2 запроса.^[3] Эта гипотеза утверждает, что лучший алгоритм для проверки любого нетривиального монотонного свойства должен (в худшем случае) запрашивать все возможные ребра. Эта гипотеза все еще остается открытой, хотя некоторые специальные свойства графов оказались непонятными для всех. п. Гипотеза разрешена для случая, когда п это основная сила к Кан, Сакс и Стертевант (1983) с помощью топологический подход. Гипотеза также была разрешена для всех нетривиальных монотонных свойств двудольных графов с помощью Яо (1988). Незначительный -закрытые свойства также показали себя уклончивыми для больших п (Чакрабарти, Хот и Ши 2001 ).

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

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

Ричард Карп также предположил, что Ω (п²) запросы требуются для проверки нетривиальных монотонных свойств, даже если разрешены рандомизированные алгоритмы. Неизвестно нетривиальное свойство монотонности, требующее менее п²/ 4 запроса для тестирования. Линейная нижняя граница (т. Е. Ω (п)) по всем монотонным свойствам следует из очень общего взаимосвязь между рандомизированной и детерминированной сложностями запроса. Первая суперлинейная нижняя оценка всех монотонных свойств была дана формулой Яо (1991) который показал, что Ω (п бревно^1/12 п) запросы обязательны. Это было дополнительно улучшено Король (1988) к Ω (п^5/4), а затем по Хайнал (1991) к Ω (п^4/3). Впоследствии это было улучшено до самой известной на данный момент нижней границы (среди оценок, которые выполняются для всех монотонных свойств) Ω (п^4/3 бревно^1/3 п) к Чакрабарти и Хот (2001).

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

Как и в детерминированном случае, существует множество специальных свойств, для которых Ω (п²) нижняя оценка известна. Более того, известны более точные нижние оценки для нескольких классов свойств графов. Например, для проверки того, имеет ли граф подграф, изоморфный какому-либо заданному графу (так называемый изоморфизм подграфов задача), наиболее известной нижней оценкой является Ω (п^3/2) из-за Грёгер (1992).

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

Для ограниченной ошибки сложность квантового запроса, наиболее известная нижняя граница - это Ω (п^2/3 бревно^1/6 п) по наблюдениям Эндрю Яо.^[4] Он получается путем комбинирования рандомизированной нижней границы с квантовым методом противника. Наилучшая нижняя граница, на которую можно надеяться, - это Ω (п), в отличие от классического случая, за счет Алгоритм Гровера что дает O (п) алгоритм запроса для проверки монотонности свойства непустоты. Подобно детерминированному и рандомизированному случаю, есть некоторые свойства, которые, как известно, имеют Ω (п) нижняя граница, например непустота (что следует из оптимальности алгоритма Гровера) и свойство содержать треугольник. Известно, что некоторые свойства графа имеют Ω (п^3/2) нижнюю границу и даже некоторые свойства с Ω (п²) нижняя граница. Например, для монотонности непланарности требуется Θ (п^3/2) запросы (Ambainis et al. 2008 г. ), а монотонное свойство содержать более половины возможного числа ребер (также называемое функцией большинства) требует Θ (п²) запросы (Beals et al. 2001 г. ).

Примечания

1. Триеш (1996)
2. Лутц (2001)
3. Козлова (2008 г., стр. 226–228).
4. Результат не опубликован, но упоминается в Магнез, Санта и Сегеди (2005).

Рекомендации

• Амбайнис, Андрис; Ивама, Кадзуо; Наканиши, Масаки; Нисимура, Харумичи; Раймонд, Руди; Тани, Сейитиро; Ямасита, Шигеру (2008), "Квантовая сложность запросов булевых функций с малыми наборами", Материалы 19-го Международного симпозиума по алгоритмам и вычислениям, Конспект лекций по информатике, 5369, Голд-Кост, Австралия: Springer-Verlag, стр. 907–918, Дои:10.1007/978-3-540-92182-0_79, ISBN  978-3-540-92181-3.
• Билс, Роберт; Бурман, Гарри; Клив, Ричард; Моска, Микеле; де Вольф, Рональд (2001), "Квантовые нижние оценки полиномами", Журнал ACM, 48 (4): 778–797, arXiv:Quant-ph / 9802049, Дои:10.1145/502090.502097.
• Бест, М.Р .; ван Эмде Боас, П.; Ленстра, Х.В. (1974), Уточненная версия гипотезы Аандераа-Розенберга, Отчет ZW 30/74, Mathematisch Centrum Amsterdam, HDL:1887/3792.
• Чакрабарти, Амит; Хот, Субхаш (2001), "Улучшенные нижние оценки рандомизированной сложности свойств графа", Материалы 28-го Международного коллоквиума по автоматам, языкам и программированию, Конспект лекций по информатике, 2076, Springer-Verlag, стр. 285–296, Дои:10.1007/3-540-48224-5_24, ISBN  978-3-540-42287-7.
• Чакрабарти, Амит; Хот, Субхаш; Ши Яоюнь (2001), «Уклончивость включения подграфов и связанных свойств», SIAM Журнал по вычислениям, 31 (3): 866–875, CiteSeerX  10.1.1.29.3131, Дои:10.1137 / S0097539700382005.
• Фридгут, Эхуд; Кан, Джефф; Вигдерсон, Ави (2002), «Вычисление свойств графа с помощью рандомизированных разбиений субкубов», Методы рандомизации и аппроксимации в компьютерных науках, Конспект лекций по информатике, 2483, Springer-Verlag, п. 953, г. Дои:10.1007/3-540-45726-7_9, ISBN  978-3-540-44147-2.
• Грёгер, Ганс Дитмар (1992), «О рандомизированной сложности свойств монотонного графа» (PDF), Acta Cybernetica, 10 (3): 119–127.
• Хайнал, Петер (1991), "An Ω (п^4/3) нижняя оценка рандомизированной сложности свойств графа », Комбинаторика, 11 (2): 131–143, Дои:10.1007 / BF01206357.
• Кан, Джефф; Сакс, Михаил; Стертевант, Дин (1983), "Топологический подход к уклончивости", 24-й ежегодный симпозиум по основам компьютерных наук (sfcs 1983), Лос-Аламитос, Калифорния, США: Компьютерное общество IEEE, стр. 31–33, Дои:10.1109 / SFCS.1983.4, ISBN  978-0-8186-0508-6.
• Король, Валери (1988), "Нижние оценки сложности свойств графа", Proc. 20-й симпозиум ACM по теории вычислений, Чикаго, Иллинойс, США, стр. 468–476, Дои:10.1145/62212.62258, ISBN  978-0-89791-264-8.
• Клейтман, Д.Дж.; Квятковский, DJ (1980), "Дальнейшие результаты по гипотезе Аандераа-Розенберга", Журнал комбинаторной теории, серия B, 28: 85–95, Дои:10.1016 / 0095-8956 (80) 90057-Х.
• Козлов, Дмитрий (2008), Комбинаторная алгебраическая топология, Springer-Verlag, ISBN  978-3-540-73051-4.
• Лутц, Франк Х. (2001), "Некоторые результаты, связанные с гипотезой уклончивости", Журнал комбинаторной теории, серия B, 81 (1): 110–124, Дои:10.1006 / jctb.2000.2000.
• Корнеффель, Торстен; Триеш, Эберхард (2010), "Асимптотическая оценка сложности свойств монотонного графа", Комбинаторика, Springer-Verlag, 30 (6): 735–743, Дои:10.1007 / s00493-010-2485-3, ISSN  0209-9683.
• Магнье, Фредерик; Сантха, Миклош; Сегеди, Марио (2005), «Квантовые алгоритмы для задачи треугольника», Материалы шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Ванкувер, Британская Колумбия: Общество промышленной и прикладной математики, стр. 1109–1117, arXiv:Quant-ph / 0310134, Bibcode:2003квант.ч.10134М.
• О'Доннелл, Райан; Сакс, Михаил; Шрамм, Одед; Серведио, Рокко А. (2005), «Каждое дерево решений имеет влиятельную переменную», Протокол 46-го симпозиума IEEE по основам информатики, стр. 31–39, arXiv:cs / 0508071, Дои:10.1109 / SFCS.2005.34, ISBN  978-0-7695-2468-9.
• Ривест, Рональд Л.; Вюймен, Жан (1975), "Обобщение и доказательство гипотезы Аандераа-Розенберга", Proc. 7-й симпозиум ACM по теории вычислений, Альбукерке, Нью-Мексико, США, стр. 6–11, CiteSeerX  10.1.1.309.7236, Дои:10.1145/800116.803747.
• Розенберг, Арнольд Л. (1973), «О времени, необходимом для распознавания свойств графов: проблема», Новости SIGACT, 5 (4): 15–16, Дои:10.1145/1008299.1008302.
• Шайдвайлер, Роберт; Триеш, Эберхард (2013), "Нижняя граница сложности свойств монотонного графа", Журнал SIAM по дискретной математике, 27 (1): 257–265, Дои:10.1137/120888703
• Триеш, Эберхард (1996), "О сложности распознавания некоторых свойств графа", Комбинаторика, 16 (2): 259–268, Дои:10.1007 / BF01844851.
• Яо, Эндрю Чи-Чи (1988), "Свойства монотонного двудольного графа неуловимы", SIAM Журнал по вычислениям, 17 (3): 517–520, Дои:10.1137/0217031.
• Яо, Эндрю Чи-Чи (1991), "Нижние оценки рандомизированных алгоритмов свойств графа", Журнал компьютерных и системных наук, 42 (3): 267–287, Дои:10.1016 / 0022-0000 (91) 90003-Н.

дальнейшее чтение

• Боллобаш, Бела (2004), «Глава VIII. Сложность и упаковка», Экстремальная теория графов, Нью-Йорк: Dover Publications, стр. 401–437, ISBN  978-0-486-43596-1.
• Ловас, Ласло; Янг, Нил Э. (2002), "Конспект лекций об уклончивости свойств графа", arXiv:cs / 0205031v1
• Хронаки, Екатерина Е (1990), Обзор уклончивости: нижние границы сложности дерева решений булевых функций, CiteSeerX  10.1.1.37.1041.
• Майкл Сакс. «Деревья решений: проблемы и результаты, старые и новые» (PDF).