Естественный кандидат против гипотезы об изоморфизме?

Знаменитая гипотеза об изоморфизме Бермана и Хартманиса говорит, что все -полные языки полиномиально по времени изоморфны (p-изоморфны) друг другу. Ключевое значение гипотезы является то , что она предполагает . Она была опубликована в 1977 году, и часть подтверждающих доказательств, что все -полные проблемы , известные в то время были действительно р-изоморфно. На самом деле все они были дополнены , что является хорошим естественным свойством и подразумевает p-изоморфизм нетривиальным образом. $NP$ $P\neq NP$ $NP$

С тех пор доверие к гипотезе ухудшилось, потому что были обнаружены кандидаты в полных языков, которые вряд ли будут p-изоморфны , хотя проблема все еще остается открытой. Однако, насколько мне известно, ни один из этих кандидатов не представляет естественных проблем; они построены с помощью диагонализации с целью опровержения гипотезы об изоморфизме. $NP$ $SAT$

Правда ли, что спустя почти четыре десятилетия все известные естественные -полные проблемы p-изоморфны ? Или есть предположительный естественный кандидат на обратное? $NP$ $SAT$

cc.complexity-theory complexity-classes p-vs-np np-complete Андрас Фараго
источник

Я воздержусь от голосования, но я лично против всех вопросов, которые требуют существования чего-то «естественного», не определяя, что является естественным. Я не говорю, что я против всех "нечетких" понятий, но я думаю, что естественный слишком широк, и необходимо конкретизировать более конкретное желательное / нежелательное свойство.

Сашо Николов

+1 Хороший вопрос. @SashoNikolov, до изобретения машин Тьюринга, формальное определение алгоритмов, интуитивное понятие было известно и использовалось в течение тысяч лет. Отсутствие формального определения естественной проблемы не должно удерживать нас от неформального использования. Естественная проблема - это концепция, которую вы знаете, когда видите это.

Мохаммад Аль-Туркистани

Я согласен с Мухаммедом в том, что вы обычно знаете естественную проблему, когда видите ее. Однако «естественный» также зависит от контекста, и в некоторых контекстах есть более четкое понятие - или, возможно, просто более согласованный и большой набор явно естественных примеров - чем в других. Я думаю, что этот конкретный случай (NP-полная) проблемы попадает в первый класс. Например, применение односторонней функции к SAT для получения другой NP-полной задачи (основная идея некоторых кандидатов, нарушающих Бермана-Хартманиса) явно приводит к «неестественной» проблеме.

Джошуа Грохов

Проблема с «естественным» на практике здесь, на cstheory.SE, заключается в том, что этот вопрос обычно приводит к шторму «нет истинного шотландца», где каждый ответ, который не нравится ОП, считается «неестественным» для развивающегося / меняющегося множества причин.

Суреш Венкат

@Sasho, я лично читаю «естественный» без дальнейшего разъяснения как означающий: это не искусственно созданная проблема, чтобы ответить на вопрос (или подобные), люди интересуются проблемой независимо.

Kaveh

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

Основная причина заключается в том, что типично естественные NP-полные проблемы очень легко увидеть как дополняемые, что, как показали Берман и Хартманис, достаточно изоморфно SAT. Для задач, связанных с естественным графом, это обычно включает добавление дополнительных вершин, которые, например, отсоединены от графа или связаны очень специфическим (но обычно очевидным) способом. Для решения проблем оптимизации обычно требуется добавление новых фиктивных переменных без каких-либо ограничений для них. И так далее.

Джошуа Грохов
источник

Да, в большинстве задач с графами заполнение легко. Но это не всегда так. Пример: правда ли, что граф свободен от треугольников и имеет гамильтонов путь? Здесь, чтобы сохранить свойство, новая вершина заполнения должна соединяться с некоторым старым (чтобы разрешить гамильтонов путь), она должна соединяться с независимым набором (чтобы избежать создания треугольника), и этот независимый набор должен быть таким, чтобы он содержал конечную точку по крайней мере одного гамильтонова пути (чтобы сделать его продолжаемым до новой вершины). Мне не кажется очевидным, как этого добиться. Конечно, можно найти какой-то другой способ набить, я не уверен.

Андрас Фараго

Гамильтонов путь, см. Оригинальную статью Бермана-Хартманиса (Thm 7 (5) в версии STOC, Thm 8 (5) в версии журнала: dx.doi.org/10.1137/0206023 ). Их конструкция не вводит никаких новых направленных 3-циклов. Если вы хотите избежать даже ненаправленных треугольников, вы можете подразделить некоторые ребра в их построении новыми вершинами. Вы также можете найти интересную статью, в которой они показывают, что квадратичные диофантовы уравнения являются p-iso для SAT: dx.doi.org/10.1016/0022-0000(78)90027-2

Джошуа

@JoshuaGrochow Есть ли кандидатский пример против гипотезы ЧД?

T ....

@Turbo: Да, наборы k-креативов («зашифрованные комплекты») Джозефа и Янга 1985 года: dx.doi.org/10.1016/0304-3975(85)90140-9

Джошуа

Естественный кандидат против гипотезы об изоморфизме?

Ответы: