Введение

Задача вычисления полных подграфов

В информатике проблема клики — это вычислительная задача поиска клик (подмножеств вершин, все из которых смежны друг с другом, также называемых полными подграфами) в графе. Она имеет несколько различных формулировок в зависимости от того, какие клики и какую информацию о кликах необходимо найти. Распространенные формулировки проблемы клики включают поиск максимальной клики (клики с наибольшим возможным числом вершин), поиск максимальной клики с максимальным весом во взвешенном графе, перечисление всех максимальных клик (клики, которые нельзя расширить) и решение задачи проверки, содержит ли граф клику размером больше заданного. Проблема клики возникает в следующих реальных сценариях. Рассмотрим социальную сеть, где вершины графа представляют людей, а ребра графа — взаимные знакомства. Тогда клика представляет собой подмножество людей, которые все друг друга знают, и алгоритмы поиска клик могут быть использованы для выявления этих групп общих друзей. Помимо применения в социальных сетях, проблема клики также имеет множество применений в биоинформатике и вычислительной химии. Большинство вариантов проблемы клики являются сложными. Задача проверки на наличие клики является NP-полной (одна из 21 NP-полных задач Карпа). Задача поиска максимальной клики является одновременно неразрешимой для фиксированных параметров и сложной для аппроксимации. Кроме того, перечисление всех максимальных клик может потребовать экспоненциального времени, поскольку существуют графы с экспоненциально большим количеством максимальных клик. Поэтому значительная часть теории, посвященной проблеме клики, направлена на выявление специальных типов графов, для которых существуют более эффективные алгоритмы, или на установление вычислительной сложности общей задачи в различных моделях вычислений. Для поиска максимальной клики можно систематически перебирать все подмножества, но такой перебор является слишком трудоемким для практического применения к сетям, состоящим из более чем нескольких десятков вершин. Хотя алгоритма полиномиального времени для этой задачи не известно, существуют более эффективные алгоритмы, чем полный перебор. Например, алгоритм Брона — Кербоша можно использовать для перечисления всех максимальных клик за оптимальное время в худшем случае, а также можно перечислить их за полиномиальное время на каждую клику.

История и применение

Изучение полных подграфов в математике предшествует терминологии "клики". Например, полные подграфы впервые появляются в математической литературе в графовой переформулировке теории Рамзея. Однако термин "клика" и задача алгоритмического перечисления клик берут свое начало в социальных науках, где полные подграфы используются для моделирования социальных клик – групп людей, все члены которых знакомы друг с другом. Они использовали графы для моделирования социальных сетей и адаптировали терминологию социальных наук к теории графов, впервые назвав полные подграфы "кликами". Первый алгоритм для решения задачи о клике принадлежит , и его разработка была мотивирована социологическим применением. Исследователи в области социальных наук также определили различные типы клик и максимальных клик в социальных сетях, как "сплоченные подгруппы" людей или акторов в сети, все из которых связаны одним из нескольких видов отношений. Многие из этих обобщенных понятий о кликах можно найти, построив неориентированный граф, ребра которого представляют связанные пары акторов из социальной сети, а затем применив алгоритм для решения задачи о клике к этому графу. После работы Харари и Росса многие другие разработали алгоритмы для различных вариантов задачи о клике. В этих приложениях строится граф, в котором каждая вершина представляет собой пару соответствующих атомов, по одному из каждой из двух молекул. Две вершины соединяются ребром, если соответствующие им соответствия совместимы друг с другом. Совместимость может означать, например, что расстояния между атомами в двух молекулах примерно равны, в пределах заданной погрешности. Клика в этом графе представляет собой набор пар соответствующих атомов, в которых все соответствия совместимы друг с другом. Особым случаем этого метода является использование модульного произведения графов для сведения задачи нахождения максимального общего индуцированного подграфа двух графов к задаче нахождения максимальной клики в их произведении. В автоматическом тестировании схем поиск клик может помочь ограничить размер тестового набора. В биоинформатике алгоритмы поиска клик использовались для построения эволюционных деревьев, предсказания структуры белков и поиска тесно взаимодействующих кластеров белков. Перечисление клик в графе зависимостей является важным шагом в анализе определенных случайных процессов. В математике гипотеза Келлера о замощении гиперкубов была опровергнута , который использовал алгоритм поиска клик на ассоциированном графе для нахождения контрпримера.

Определения

Ненаправленный граф формируется конечным набором вершин и набором неупорядоченных пар вершин, называемых ребрами. По соглашению, при анализе алгоритмов число вершин в графе обозначается как n, а число ребер – как m. Клика в графе G – это полный подграф G. То есть, это подмножество K вершин, такое что любые две вершины в K являются конечными точками ребра в G. Максимальная клика – это клика, к которой нельзя добавить больше вершин. Для каждой вершины v, не входящей в максимальную клику, должна существовать другая вершина w, которая входит в клику и не смежна с v, что препятствует добавлению v в клику. Максимальная клика – это клика, включающая наибольшее возможное число вершин. Число клики ω(G) – это число вершин в максимальной клике G. В задаче о максимальной клике на вход подается ненаправленный граф, а на выходе – максимальная клика в этом графе. Если существует несколько максимальных клик, можно выбрать любую из них. Поэтому многие вычислительные результаты применимы одинаково хорошо к обеим задачам, и некоторые исследовательские работы не проводят четкого различия между ними. Однако эти две задачи обладают разными свойствами применительно к ограниченным семействам графов. Например, задача о клике может быть решена за полиномиальное время для планарных графов, в то время как задача о независимом множестве остается NP-трудной для планарных графов.

Найти одну максимальную клику

Максимальная клика, иногда называемая кликой, максимальной по включению, — это клика, которая не является подмножеством большей клики. Следовательно, любая клика содержится в некоторой максимальной клике. Максимальные клики могут быть очень маленькими. Граф может содержать не максимальную клику с большим количеством вершин и отдельную клику размера 2, которая является максимальной. В то время как максимальная (то есть самая большая) клика обязательно является максимальной, обратное неверно. Существуют типы графов, в которых каждая максимальная клика также является максимальной; это дополнения хорошо покрытых графов, в которых каждое максимальное независимое множество является максимальным. Однако в других графах существуют максимальные клики, которые не являются максимальными. Одну максимальную клику можно найти с помощью простого жадного алгоритма. Начиная с произвольной клики (например, с любой отдельной вершины или даже с пустого множества), расширяйте текущую клику, добавляя по одной вершине, последовательно просматривая оставшиеся вершины графа. Для каждой вершины v, которую рассматривает этот цикл, добавляйте v к клике, если она смежна со всеми вершинами, которые уже находятся в клике, и отбрасывайте v в противном случае. Этот алгоритм выполняется за линейное время. Благодаря простоте поиска максимальных кличек и их потенциально небольшому размеру, больше внимания уделяется гораздо более сложной алгоритмической задаче поиска максимальной или, по крайней мере, большой клики. Однако некоторые исследования в области параллельных алгоритмов посвящены задаче поиска максимальной клики. В частности, задача поиска лексикографически первой максимальной клики (которая находится с помощью описанного выше алгоритма) была доказана как полная для класса полиномиальных функций. Этот результат подразумевает, что задача вряд ли может быть решена в классе параллельной сложности NC.

Клика с фиксированным размером

Можно проверить, содержит ли граф G k-вершинную клику, и найти любую такую клику, которую он содержит, используя алгоритм полного перебора. Этот алгоритм исследует каждый подграф с k вершинами и проверяет, образует ли он клику. Это требует времени, выражаемого с помощью нотации «большое O». Это связано с тем, что необходимо проверить подграфов, каждый из которых имеет ребер, присутствие которых в G нужно проверить. Таким образом, задача может быть решена за полиномиальное время, когда k является фиксированной константой. Однако, когда k не имеет фиксированного значения, а может изменяться как часть входных данных, время становится экспоненциальным. Самый простой нетривиальный случай задачи поиска клики — это поиск треугольника в графе или, эквивалентно, определение того, является ли граф лишенным треугольников. В графе G с m ребрами может быть не более Θ(m^(3/2)) треугольников (используя нотацию «большая тета», чтобы указать, что эта граница точна). Наихудший случай для этой формулы возникает, когда сам G является кликой. Следовательно, алгоритмы для перечисления всех треугольников должны занимать не менее Ω(m^(3/2)) времени в наихудшем случае (используя нотацию «большое омега»), и известны алгоритмы, соответствующие этой временной сложности. Например, опишите алгоритм, который сортирует вершины в порядке убывания степени и затем перебирает каждую вершину v в отсортированном списке, ища треугольники, включающие v и не включающие никакую предыдущую вершину в списке. Для этого алгоритм помечает всех соседей v, просматривает все ребра, инцидентные соседу v, выводя треугольник для каждого ребра с двумя помеченными конечными точками, а затем удаляет пометки и удаляет v из графа. Как показывают авторы, время работы этого алгоритма пропорционально древовидности графа (обозначаемой a(G)), умноженной на количество ребер, то есть, поскольку древовидность не превышает , этот алгоритм работает за время. В более общем случае все k-вершинные клики могут быть перечислены аналогичным алгоритмом, требующим времени пропорционального количеству ребер, умноженному на древовидность в степени (k − 2). Для графов с постоянной древовидностью, таких как планарные графы (или, в общем случае, графы из любого нетривиального минорно-замкнутого семейства графов), этот алгоритм занимает время, что оптимально, поскольку оно линейно относительно размера входных данных. Если требуется только один треугольник или гарантия того, что граф лишен треугольников, возможны более быстрые алгоритмы. Как отмечают, граф содержит треугольник тогда и только тогда, когда его матрица смежности и квадрат матрицы смежности содержат ненулевые элементы в одной и той же ячейке. Следовательно, методы быстрого умножения матриц могут быть применены для поиска треугольников за время. Быстрое умножение матриц использовалось для улучшения алгоритма поиска треугольников до. Эти алгоритмы, основанные на быстром умножении матриц, также были расширены на задачи поиска k-кликов для больших значений k.

Список всех максимальных группировок

В результате, каждый граф с n вершинами имеет не более 3^(n/3) максимальных клик. Их можно перечислить с помощью алгоритма Брон–Кербоша, рекурсивной процедуры с возвратом. Основная рекурсивная подпрограмма этой процедуры имеет три аргумента: частично построенная (немаксимальная) клика, множество вершин-кандидатов, которые могут быть добавлены в клику, и другое множество вершин, которые не следует добавлять (потому что это привело бы к клике, которая уже была найдена). Алгоритм пытается добавлять вершины-кандидаты по одной к частичной клике, выполняя рекурсивный вызов для каждой из них. После попытки добавления каждой из этих вершин он перемещает её в множество вершин, которые не следует добавлять повторно. Можно показать, что варианты этого алгоритма имеют наихудшее время работы, соответствующее количеству клик, которые могут потребоваться для перечисления. Следовательно, это обеспечивает оптимальное решение в наихудшем случае для задачи перечисления всех максимальных клик. Кроме того, алгоритм Брон–Кербоша широко известен как более быстрый на практике, чем его альтернативы. Однако, когда количество клик значительно меньше, чем в наихудшем случае, другие алгоритмы могут быть предпочтительнее. Как было показано, также возможно перечислить все максимальные клики в графе за время, полиномиальное относительно размера генерируемой клики. Такой алгоритм, в котором время работы зависит от размера вывода, известен как алгоритм, чувствительный к объему вывода. Их алгоритм основан на следующих двух наблюдениях, связывающих максимальные клики данного графа G с максимальными кликами графа G \ v, полученного удалением произвольной вершины v из G: Для каждой максимальной клики K графа G \ v, либо K продолжает формировать максимальную клику в G, либо K ⋃ {v} формирует максимальную клику в G. Следовательно, граф G имеет не менее столько же максимальных клик, сколько граф G \ v. Каждая максимальная клика в G, не содержащая v, является максимальной кликой в G \ v, и каждая максимальная клика в G, содержащая v, может быть сформирована из максимальной клики K в G \ v путем добавления v и удаления вершин, не являющихся соседями v, из K. Используя эти наблюдения, они могут генерировать все максимальные клики в G с помощью рекурсивного алгоритма, который произвольно выбирает вершину v, а затем для каждой максимальной клики K в G \ v выводит как K, так и клику, сформированную путем добавления v к K и удаления вершин, не являющихся соседями v. Однако некоторые клики в G могут быть сгенерированы таким образом из более чем одной родительской клики в G \ v, поэтому они устраняют дубликаты, выводя клику в G только тогда, когда её родитель в G \ v является лексикографически максимальным среди всех возможных родительских клик. На основе этого принципа они показывают, что все максимальные клики в G могут быть сгенерированы за время, пропорциональное размеру клики, где m — количество ребер в G, а n — количество вершин. Это можно улучшить до O(ma) за клику, где a — древовидность данного графа. Представлен альтернативный алгоритм, основанный на быстром умножении матриц. Показано, что даже можно перечислить все максимальные клики в лексикографическом порядке с полиномиальной задержкой за клику. Однако выбор порядка важен для эффективности этого алгоритма: для обратного порядка не существует алгоритма с полиномиальной задержкой, если P = NP. На основе этого результата можно перечислить все максимальные клики в полиномиальное время для семейств графов, в которых количество клик полиномиально ограничено. Эти семейства включают хордальные графы, полные графы, графы без треугольников, интервальные графы, графы с ограниченной боксичностью и планарные графы. В частности, планарные графы имеют клики, размер которых не превышает постоянную величину, которые могут быть перечислены за линейное время. То же самое верно для любого семейства графов, которые одновременно разрежены (имеют количество ребер, не превышающее постоянное число вершин) и замкнуты относительно операции взятия подграфов. Также рассматриваются локальный поиск, жадные алгоритмы и ограничено-ориентированное программирование. Нестандартные вычислительные методологии, предложенные для поиска клик, включают вычисления на ДНК и адиабатические квантовые вычисления. Задача о максимальной клике была предметом соревновательной реализации, спонсируемой DIMACS в 1992–1993 годах, и коллекция графов, использованных в качестве эталонов для соревнования, находится в открытом доступе.

Специальные классы графиков

Плоскостные графы и другие семейства разреженных графов были рассмотрены выше: они имеют линейное число максимальных кличек ограниченного размера, которые можно перечислить за линейное время. Предлагается альтернативный алгоритм с квадратичной временной сложностью для поиска максимальных кличек в графах сопоставимости – более широком классе совершенных графов, включающем графы перестановок как частный случай. В хордальных графах максимальные клики можно найти, перечислив вершины в порядке исключения и проверяя окрестности клики каждой вершины в этом порядке. В некоторых случаях эти алгоритмы можно расширить и на другие, несовершенные классы графов. Например, в круговом графе окрестность каждой вершины является графом перестановок, поэтому максимальную клику в круговом графе можно найти, применив алгоритм для графов перестановок к каждой окрестности. Аналогично, в графе единичных дисков (с известным геометрическим представлением) существует алгоритм полиномиального времени для поиска максимальных кличек, основанный на применении алгоритма для дополнений двудольных графов к общим окрестностям пар вершин. Алгоритмическая задача поиска максимальной клики в случайном графе, полученном из модели Эрдоша — Рени (в которой каждое ребро появляется с вероятностью 1/2, независимо от других ребер), была предложена. Поскольку максимальная клика в случайном графе с высокой вероятностью имеет логарифмический размер, её можно найти полным перебором в ожидаемое время. Это квазиполиномиальная временная сложность. Хотя кликовое число таких графов обычно очень близко к 2 log₂n, простые жадные алгоритмы, а также более сложные методы рандомизированного приближения находят клики размером log₂n, вдвое меньшим. Количество максимальных кличек в таких графах с высокой вероятностью экспоненциально относительно log²n, что не позволяет методам, перечисляющим все максимальные клики, работать за полиномиальное время. Из-за сложности этой задачи несколько авторов исследовали задачу о скрытой клике – задачу поиска клики в случайных графах, к которым добавлены большие клики. В то время как спектральные методы и полудефинитное программирование могут обнаруживать скрытые клики размера , в настоящее время не известно алгоритмов полиномиального времени для обнаружения клик размера (выраженных с использованием нотации "маленькое о").

Алгоритмы приближения

Несколько авторов рассматривали алгоритмы приближения, которые пытаются найти клику или независимое множество, размер которых, хотя и не максимальный, максимально приближен к максимальному размеру, достижимому за полиномиальное время. Хотя большая часть этих работ была посвящена независимым множествам в разреженных графах, что не имеет смысла для сопряженной задачи о клике, также проводились исследования алгоритмов приближения, не использующих предположения о разреженности. В работе [укажите автора/работу, если известно] описан алгоритм, работающий за полиномиальное время, который находит клику размером Ω((log n / log log n)² ) в любом графе, имеющем число клики Ω(n / logᵏ n) для любой константы k. Используя этот алгоритм, когда число клики заданного входного графа находится в диапазоне от n/log n до n/log³ n, переключаясь на другой алгоритм для графов с большим числом клики и выбирая клику из двух вершин, если оба алгоритма не находят решения, Фейге предлагает алгоритм приближения, который находит клику с числом вершин, отличающимся от максимального не более чем в O(n(log log n)² / log³ n) раз. Хотя коэффициент приближения этого алгоритма невелик, на сегодняшний день он является наилучшим известным. Результаты, касающиеся сложности приближения, описанные ниже, указывают на то, что не существует алгоритма приближения с коэффициентом приближения, значительно меньшим, чем линейный.

NP-полность

Проблема поиска клики NP-полна. Она была одной из 21 исходных задач, предложенных Ричардом Карпом для демонстрации NP-полноты в его статье 1972 года «Сократимость между комбинаторными задачами». Эта проблема также упоминалась в работе Стивена Кука, представляющей теорию NP-полных задач. В силу сложности задачи принятия решения, задача нахождения максимальной клики также является NP-трудной. Если бы удалось решить её, можно было бы решить и задачу принятия решения, сравнив размер максимальной клики с заданным размером в задаче принятия решения. Доказательство NP-полноты Карпа представляет собой много-к-одному сокращение из задачи булевой выполнимости. В нём описывается, как преобразовать булевы формулы в конъюнктивной нормальной форме (КНФ) в эквивалентные экземпляры задачи поиска максимальной клики. Выполнимость, в свою очередь, была доказана NP-полной в теореме Кука — Левина. Начиная с заданной формулы КНФ, Карп строит граф, имеющий вершину для каждой пары (v, c), где v — переменная или её отрицание, а c — пункт формулы, содержащий v. Две из этих вершин соединены ребром, если они представляют собой совместимые назначения значений переменным для разных пунктов. То есть, существует ребро от (v, c) к (u, d) всякий раз, когда c ≠ d и u и v не являются отрицаниями друг друга. Если k обозначает количество пунктов в формуле КНФ, то k-вершинные клики в этом графе представляют собой непротиворечивые способы присвоения истинных значений некоторым переменным для удовлетворения формулы. Следовательно, формула выполнима тогда и только тогда, когда существует k-вершинная клика. Некоторые NP-полные задачи (например, задача коммивояжёра в планарных графах) могут быть решены за время, экспоненциальное относительно сублинейной функции от размера входных данных n, что значительно быстрее, чем полный перебор. Однако маловероятно, что для задачи поиска клики в произвольных графах возможно найти подобную субекспоненциальную оценку времени, поскольку это привело бы к аналогичным субекспоненциальным оценкам для многих других стандартных NP-полных задач.

Сложность схемы

Вычислительная сложность задачи о клике привела к тому, что она использовалась для доказательства нескольких нижних оценок сложности булевых схем. Существование клики заданного размера является монотонным свойством графа, то есть, если клика существует в данном графе, она будет существовать и в любом его надграфе. Поскольку это свойство монотонно, должна существовать монотонная схема, использующая только логические элементы И и ИЛИ, для решения задачи определения наличия клики заданного фиксированного размера. Однако размер таких схем может быть доказан как сверхполиномиальная функция от числа вершин и размера клики, экспоненциальная относительно кубического корня из числа вершин. Даже если допускается небольшое количество элементов НЕ, сложность остаётся сверхполиномиальной. Кроме того, глубина монотонной схемы для задачи о клике, использующей элементы с ограниченным числом входов, должна быть не меньше, чем полином от размера клики.

Сложность дерева решений

(Детерминированная) сложность дерева решений для определения свойства графа – это количество вопросов вида "Существует ли ребро между вершиной u и вершиной v?", которые необходимо задать в худшем случае, чтобы определить, обладает ли граф данным свойством. Иными словами, это минимальная высота булевого дерева решений для данной задачи. Существует n(n–1)/2 возможных вопросов. Следовательно, любое свойство графа может быть определено максимум n(n–1)/2 вопросами. Также можно определить случайную и квантовую сложность дерева решений для свойства – ожидаемое количество вопросов (для входных данных в худшем случае), на которые рандомизированному или квантовому алгоритму необходимо получить ответы, чтобы правильно определить, обладает ли данный граф этим свойством. Поскольку свойство наличия клики является монотонным, оно охватывается гипотезой Андреа, Карпа и Розенберга, которая утверждает, что детерминированная сложность дерева решений для определения любого нетривиального монотонного свойства графа равна точно n(n–1)/2. Для произвольных монотонных свойств графа эта гипотеза остаётся недоказанной. Однако для детерминированных деревьев решений и для любого k в диапазоне 2 ≤ k ≤ n, было показано, что свойство наличия k-клики имеет сложность дерева решений, равную точно n(n–1)/2. Детерминированные деревья решений также требуют экспоненциального размера для обнаружения клик или большого полиномиального размера для обнаружения клик ограниченного размера. Гипотеза Андреа, Карпа и Розенберга также утверждает, что случайная сложность дерева решений для нетривиальных монотонных функций равна Θ(n²). Эта гипотеза также остаётся недоказанной, но была разрешена для свойства наличия k-клики при 2 ≤ k ≤ n. Известно, что это свойство имеет случайную сложность дерева решений Θ(n²). Для квантовых деревьев решений лучшая известная нижняя граница – Ω(n), но соответствующий алгоритм неизвестен для случая k ≥ 3.

Неизменная стойкость

Параметризованная сложность — это теоретическое изучение сложности задач, которые естественным образом снабжены небольшим целым параметром k, и для которых задача становится сложнее с увеличением k, например, поиск k клик в графах. Задача считается разрешимой за фиксированное время (fixed-parameter tractable), если существует алгоритм для её решения на входах размера n и функция f, такая что алгоритм работает за время То есть, задача разрешима за фиксированное время, если её можно решить за полиномиальное время для любого фиксированного значения k и, кроме того, показатель полинома не зависит от k. Для поиска k вершинных клик алгоритм полного перебора имеет время работы O(n^k * k^2). Поскольку показатель степени n зависит от k, этот алгоритм не является разрешимым за фиксированное время. Хотя его можно улучшить с помощью быстрого умножения матриц, время работы всё равно имеет показатель, линейный относительно k. Таким образом, хотя время работы известных алгоритмов для задачи о клике является полиномиальным для любого фиксированного k, этих алгоритмов недостаточно для достижения разрешимости за фиксированное время. предложили иерархию параметризованных задач, иерархию W, и предположили, что для неё не существует алгоритмов, разрешимых за фиксированное время. Они доказали, что задача о независимом множестве (или, эквивалентно, о клике) является сложной для первого уровня этой иерархии, W[1]. Следовательно, согласно их предположению, для клики не существует алгоритма, разрешимого за фиксированное время. Более того, этот результат служит основой для доказательств W[1]-трудности многих других задач и, таким образом, является аналогом теоремы Кука — Левина для параметризованной сложности. показали, что поиск k вершинных клик не может быть выполнен за время n^(o(k)), если только неверна гипотеза об экспоненциальном времени. Это снова свидетельствует о том, что алгоритм, разрешимый за фиксированное время, невозможен. Хотя задачи перечисления максимальных клик или поиска максимальных клик вряд ли будут разрешимы за фиксированное время с параметром k, они могут быть разрешимы за фиксированное время для других параметров, определяющих сложность экземпляра. Например, известно, что обе задачи разрешимы за фиксированное время при параметризации по дегенерации входного графа.

Твердость приближения

Слабые результаты, намекающие на то, что задачу о клике сложно приближенно решить, известны уже давно. Было замечено, что поскольку число клики принимает небольшие целые значения и его точное вычисление является NP-трудным, у неё не может быть полностью полиномиальной схемы аппроксимации, если P = NP. Если бы существовала слишком точная аппроксимация, округление её значения до целого числа позволило бы получить точное число клики. Однако мало что было известно до начала 1990-х годов, когда несколько авторов начали устанавливать связь между аппроксимацией максимальных кличек и вероятностно проверяемыми доказательствами. Они использовали эти связи для доказательства результатов о сложности аппроксимации для задачи о максимальной клике. После многочисленных улучшений этих результатов теперь известно, что для любого действительного числа ε > 0 не существует алгоритма, работающего за полиномиальное время, который аппроксимирует максимальную клику с точностью лучше, чем , если только P = NP. Основная идея этих результатов о неаппроксимируемости заключается в построении графа, представляющего вероятностно проверяемую систему доказательств для NP-полной задачи, такой как задача булевой выполнимости. В вероятностно проверяемой системе доказательств доказательство представляется в виде последовательности битов. Экземпляр задачи выполнимости должен иметь допустимое доказательство тогда и только тогда, когда он выполним. Доказательство проверяется алгоритмом, который после вычисления за полиномиальное время на входе для задачи выполнимости выбирает для проверки небольшое количество случайно выбранных позиций в строке доказательства. В зависимости от значений, найденных в этой выборке битов, проверяющий либо принимает, либо отклоняет доказательство, не просматривая остальные биты. Ложноотрицательные результаты недопустимы: допустимое доказательство всегда должно быть принято. Однако недействительное доказательство может быть ошибочно принято. Для каждого недействительного доказательства вероятность его принятия проверяющим должна быть низкой.

Опросы и учебники

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Научно-исследовательские статьи

Первоначально представлен на симпозиуме 1992 года по основам информатики, Первоначально представлен на симпозиуме 1992 года по основам информатики. Исходный код.