«Где действительно серьезные проблемы»? Каковы текущие идеи по этому вопросу?

27

Я нашел эту статью очень интересной. Подводя итог: здесь обсуждается, почему на практике вы редко находите наихудший случай проблемы NP-полной. Идея в статье заключается в том, что экземпляры обычно либо сильно недооценены, либо сильно перенапряжены, и то, и другое относительно легко решить. Затем для нескольких проблем предлагается мера «ограниченности». Эти проблемы, как представляется, имеют «фазовый переход» от 0 вероятности решения до 100% вероятности. Затем он выдвигает гипотезу:

  1. Все NP-полные (или даже все NP-проблемы) проблемы имеют меру «ограниченности».
  2. Что для каждой NP-полной задачи вы можете создать график вероятности решения, существующего как функция «ограниченности». Более того, этот граф будет содержать фазовый переход, где эта вероятность быстро и резко возрастает.
  3. Наихудшие примеры NP-полных задач лежат в этом фазовом переходе.
  4. Тот факт, лежит ли проблема на этом фазовом переходе, остается неизменным при преобразовании одной NP-полной задачи в другую.

Эта статья была опубликована в 1991 году. Мой вопрос: проводились ли последующие исследования этих идей за последние 25 лет? И если так, то что думает о них нынешний мейнстрим? Были ли они найдены правильными, неправильными, не относящимися к делу?

dimpol
источник
Случайные случаи CSP, k-sat, k-окраски были широко изучены сообществом TCS. Например, тот факт, что плотность / «ограниченность», при которой мы можем эффективно решить конкретную проблему, часто ниже порога, при котором вероятность существующего решения возрастает от 1 до 0 whp, привлекает большое внимание.
JWM
При какой вероятности лежит порог «легкой разрешимости» (грубо говоря)? Это больше похоже на 0,2 или больше на 0,001?
димпол
1
@dimpol обычно такой точный порог не определяется. Дело в том, в какой «ограниченности» вероятность возрастает до 0 или 1 с входным размером. Типичным утверждением было бы: «Алгоритм A решает случайный экземпляр 3-SAT с переменными и предложениями с вероятностью не менее , где переходит в 1 с ». Порог - это значение для которого вероятность возрастает от стремления к 0 до стремления к 1.NΔNпNпNNΔ
Сашо Николов
думаю, что идеи были очень влиятельными в целом, и есть очень большой набор документов, связанных с этой темой, и исследования продолжаются. однако, это сквозная концепция, потому что фазовые переходы происходят в большей степени от физики и (повторяю ответ МАТ ниже), возможно, ученые-компьютерщики немного более скептически относятся к их значению, а также, возможно, это скорее эмпирическая / экспериментальная концепция. может попытаться выработать ответ в какой-то момент времени, если другие согласны с этим комментарием, но сейчас приглашаем / будем очень признательны за дальнейшее обсуждение / анализ в
чате
1
посмотрите также, насколько часто встречается фазовый переход в NP полных задачах . Уолш также считает, что острие ножа ограниченности является значительным, и за ним много не следили, оно взаимосвязано с точкой перехода, но, возможно, оно не совсем совпадает с концепцией ... в статье не упоминаются фракталы напрямую, но я думаю, что она весьма наводит на размышления в отношении самоподобие, масштабная инвариантность и т.д.
ВЗН

Ответы:

26

Вот приблизительное резюме статуса, основанное на презентации, сделанной Варди на семинаре по теории конечных и алгоритмических моделей (2012):

Было замечено, что трудные случаи лежат на фазовом переходе из недостаточно ограниченного региона. Основная гипотеза состоит в том, что существует тесная связь между фазовыми переходами и вычислительной сложностью задач NP.

Ахлиоптас-Кожа-Оглан обнаружил, что существует плотность в области удовлетворения, где пространство решений разбивается на экспоненциально много небольших кластеров. Vinay Deolalikar основал свою знаменитую попытку доказать на предположении, что разрушение подразумевает вычислительную жесткость. Доказательство Деолаликара было опровергнуто тем фактом, что XOR-SAT находится в и разрушается. Следовательно, разрушение не может быть использовано для доказательства вычислительной твердости.пNпп

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

Наконец, вот статья, опубликованная в Nature, которая исследует связь между фазовыми переходами и вычислительной твердостью K-SAT.

Мухаммед Аль-Туркистани
источник
Спасибо за обзор, жаль, что это не привело к реальным прорывам.
димпол
1
Я думаю, что разрушающие феномены могут рассматриваться как исключение класса алгоритмов, основанных на локальном поиске, которые являются основой многих эвристических алгоритмов для NP-сложных задач.
Каве
3
похожие / несколько пересмотренные доклады / видео от Vardi, 2014, фазовые переходы и вычислительная сложность , международная исследовательская станция Banff
vzn
@vzn Здорово, обязательно посмотри видео Варди.
Мухаммед Аль-Туркистани
14

Да, было много работы со времен Cheeseman, Kanefsky и Taylor в 1991 году.

Выполнение поиска обзоров фазовых переходов задач NP-Complete даст вам множество результатов. Одним из таких обзоров являются Хартманн и Вейгт [1]. Для более высокого уровня введения, см. Статьи американского ученого Брайана Хейса [2] [3].

Статья Cheesemen, Kanefsky и Taylor 1991 года - неудачный случай, когда ученые-компьютерщики не обращают внимания на математику. В статье Чизмена, Канефски и Тейлора они определили, что гамильтонов цикл имеет фазовый переход с увеличением стоимости поиска вблизи критического порога. Модель случайного графа, которую они использовали, представляла собой случайный граф Эрдоса-Реньи (вероятность с фиксированным краем или эквивалентное распределение степеней по Гауссу). Этот случай был хорошо изучен до статьи Cheeseman et al 1991 года, в которой были известны почти наверняка алгоритмы полиномиального времени для этого класса графов, даже на критическом пороге или вблизи него. «Случайные графы» Боллобаса [4] - хороший справочник. Я полагаю, что оригинальное доказательство было представлено Angliun и Valiant [5] с дальнейшими улучшениями Bollobas, Fenner и Frieze [6]. После Чизмен,

Фазовый переход для гамильтоновых циклов в случайных графах Эрдоша-Реньи существует в том смысле, что существует быстрый переход вероятности нахождения решения, но это не приводит к увеличению «внутренней» сложности нахождения гамильтоновых циклов. Почти наверняка есть алгоритмы полиномиального времени для нахождения гамильтоновых циклов в случайных графах Эрдоша-Реньи даже при критическом переходе, как в теории, так и на практике.

Распространение результатов опроса [8] имело хороший успех в нахождении удовлетворительных случаев для случайных 3-SAT очень близко к критическому порогу. Мои нынешние знания немного устарели, поэтому я не уверен, был ли достигнут какой-то значительный прогресс в поиске «эффективных» алгоритмов для неудовлетворительных случаев вблизи критического порога. 3-SAT, насколько я знаю, это один из случаев, когда «легко» решить, если он выполним и близок к критическому порогу, но неизвестен (или сложен?) В неудовлетворительном случае вблизи критического порога.

Мои знания немного устарели, но в последний раз, когда я углубленно изучал этот предмет, мне выделилось несколько вещей:

  • Гамильтонов цикл является «легким» для случайных графов Эрдоша-Реньи. Где трудные проблемы для этого?
  • Числовое разделение должно быть разрешимым, когда очень далеко в почти наверняка области вероятности 0 или 1, но не существует эффективных (насколько мне известно) эффективных алгоритмов даже для умеренных размеров экземпляров (1000 чисел по 500 бит в каждом, насколько я знаю, совершенно неразрешимы с современные алгоритмы). [9] [10]
  • 3-SAT «легок» для удовлетворительных экземпляров вблизи критического порога, даже для огромных размеров экземпляров (миллионы переменных), но трудно для неудовлетворительных экземпляров вблизи критического порога.

Я не решаюсь включить его здесь, так как я не опубликовал ни одной рецензируемой статьи, но я написал свою диссертацию.по теме. Основная идея заключается в том, что возможный класс «ансамблей случайных чисел» (гамильтоновы циклы, проблема разбиения чисел и т. Д.), Обладающих свойством «жесткой инвариантности». Устойчивые по Леви распределения являются одним из наиболее естественных распределений с таким качеством, имеющих хвосты степенного закона, и можно выбирать случайные экземпляры из ансамблей NP-Complete, которые каким-то образом включают в себя устойчивое по Леви распределение. Я привел несколько слабых доказательств того, что по своей сути сложные гамильтоновы циклы можно найти, если выбрать случайные графы с устойчивым по Леви распределением степеней вместо нормального распределения (т. Е. Эрдос-Рени). Если ничего другого, это, по крайней мере, даст вам отправную точку для обзора литературы.

[1] А. К. Хартманн и М. Вейгт. Фазовые переходы в задачах комбинаторной оптимизации: основы, алгоритмы и статистическая механика. Wiley-VCH, 2005.

[2] Б. Хейс. Самая легкая трудная проблема. Американский ученый, 90 (2), 2002.

[3] Б. Хейс. На пороге. Американский ученый, 91 (1), 2003.

[4] Б. Боллобас. Случайные графики, второе издание. Издательство Кембриджского университета, Нью-Йорк, 2001.

[5] Д. Англуин и Л.Г. Валиант. Быстрые вероятностные алгоритмы для гамильтоновых цепей и соответствий. J. Computer, Syst. Sci., 18: 155–193, 1979.

[6] Б. Боллобас, Т.И. Феннер и А.М. Фриз. Алгоритм нахождения гамильтоновых путей и циклов в случайных графах. Combinatorica, 7: 327–341, 1987.

[7] Б. Вандегриенд и Дж. Калберсон. Фазовый переход G n, m не является трудным для задачи о гамильтоновом цикле. J. of AI Research, 9: 219-245, 1998.

[8] А. Браунштейн, М. Мезард и Р. Зекчина. Распространение исследования: алгоритм удовлетворенности. Случайные структуры и алгоритмы, 27: 201–226, 2005.

[9] И. Гент и Т. Уолш. Анализ эвристики для разбиения чисел. Вычислительный интеллект, 14: 430–451, 1998.

[10] К. П. Шнорр и М. Эухнер. Сокращение базиса решетки: Усовершенствованные практические алгоритмы и решение задач с подмножеством сумм. В сборниках основ теории вычислений '91, Л. Будах, под ред. Лекционных заметок по информатике, том 529, стр. 68–85, 1991.

user834
источник
0

25 лет обучения и где текущие идеи:

+++ идея 1:

Из моего опыта в решении задач удовлетворенности я обнаружил на практике, что добавление действительного k-выражения в формулу, которую мы пытаемся решить, похоже на определение (nk) переменной qbf.

Это может показаться подходом, показывающим, что современные методы спутникового решения для NP трудоемки!

+++ идея 2:

Другая идея состоит в том, что проблема AllQBFs является реальной проблемой в логической иерархии. Проблема AllQBF заключается в следующем: создайте логическое выражение Q, которое решает все 2 ^ n qbfs формулы R. AllQBF просты, когда исходная формула R является монотонной или 2-cnf.

AllQBFs кажется правдоподобным способом показать, что QBF - это Exp, потому что Q часто экспоненциальный, поэтому оценка присваивания Q (количественная оценка исходной формулы R) является экспоненциальной. Таким образом, путь к доказательству NP - это Exp, по крайней мере, пара кирпичей.

+++ идея 3: обычные k-cnfs

Кстати, во всех исследованиях фазовых переходов пропущены регулярные k-cnfs, где число вхождений переменной (в любом направлении) фиксировано, подобно регулярным графам степеней ... Обычные k-cnfs становятся намного сложнее, чем стандартная модель, потому что все переменные выглядят одинаково с точки зрения ограничений на них.

Двадцать пять лет назад, сразу после прочтения Cheeseman, я сосредоточился на раскраске графа регулярной степени, потому что все переменные выглядят одинаково. Поэтому я буду злоупотреблять привилегией ответа здесь и буду представлять результаты двадцати пяти лет на регулярных графиках!

+++ идея 4: Золотые баллы за эталонные исследования удовлетворенности

Я изучил C раскраску D регулярных N вершинных графов достаточно широко. В следующей таблице приведены результаты Golden Point для регулярной раскраски графа.

Для высокой вероятности N случайных случаев были удовлетворительными. Для очень высокого, N ^ 2 были удовлетворительными. Для сверхвысокого числа N ^ 3 случайных экземпляров были удовлетворительными.

Золотые точки расцветки с высокой вероятностью (1 - 1 / N):

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Точки золотой окраски с очень высокой вероятностью (1 - 1 / (N ^ 2)):

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Сверхвысокой вероятности (1 - 1 / (N ^ 3)) золотые точки окрашивания:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

Запись C4D9 обозначает четыре раскраски графиков девятой степени. Это самые тяжелые случайные 4cnfs, с которыми я столкнулся за 25 лет сат-решения. Недавно я раскрасил график 172 вершины девятой степени после десяти дней времени процессора.

+++ Идея 5: C5D16N ???? Голден Пойнт предположительно существует.

Спасибо, Даниэль Пехоушек

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