Твердость и направления сокращений

9

Допустим, мы знаем, что проблема A сложная, затем мы сводим A к неизвестной проблеме B, чтобы доказать, что B также сложно.

В качестве примера: мы знаем, что 3-окраска сложна. Затем мы уменьшаем 3-окраску до 4-окраски. Сочетая один из цветов в 3-х раскрасках, вы получаете 4-х раскраски, поэтому эрго-4-раскраски трудны.

Вот как. Но почему это доказательство того, что 4-раскраска сложна? Это то, что вы можете использовать решение проблемы 4-окраски, чтобы решить проблему 3-окраски? Если так, то как? Если нет, то почему это действительное доказательство?

Бонус q: Должны ли полиномиальные сокращения идти в обоих направлениях?

Изменить: если вы сможете объяснить, почему это так, на примере вы сделаете Интернет одолжение. Я не мог найти это объяснено конкретным способом нигде.

Несчастный кот
источник
Если вы имеете дело с двумя NP-полными задачами, то да, должны быть полиномиальные сокращения, которые идут обоими способами. Во многих случаях сокращения от A до B и от B до A могут сильно отличаться друг от друга.
Джо
Если проблемы не относятся к одному и тому же классу сложности, то не может быть сокращения в обоих направлениях.
Джо

Ответы:

7

Сокращение от проблемы к другой проблеме B является преобразованием f любого экземпляра a из A в экземпляр f ( a ) из B , так чтоABfaAf(a)B

xA    f(x)B(E)

Если - преобразование, сохраняющее интересующую вас сложность (например, f - это полиномиальное преобразование, если вы рассматриваете N P -твердость), то существование алгоритма A B, решающего B, подразумевает существование алгоритма, решающего A : этого достаточно для запустить п , то Б .ffNPABBAfAB

Следовательно, существование такого уменьшения в от до B означает , что B не легче , чем A . Нет необходимости в сокращении другого пути.ABBA

Например, для раскраски графа. Вы можете уменьшить 3 цвета до 4 цветов, но не сразу. Если вы возьмете граф и выберете f ( G ) = G, то у вас будет x 3 C O Lf ( x ) 4 C O L, но у вас нет f ( x ) 4 C O Lx 3 C O L, конечно. Вывод состоит в том, что эквивалентность (Gf(G)=Gx3COL f(x)4COLf(x)4COL x3COL не соблюдается, поэтому е являетсянесокращение.(E)f

Вы можете построить правильное сокращение от 3 C O L до 4 C O L, но это немного сложнее: для любого графа G пусть f ( G ) будет графом G, расширенным другим узлом u , связанным с ребром к каждому другому узлу.f3COL4COLGf(G)Gu

  • Преобразование сохраняет сложность (здесь многочлен);
  • если в 3 C O L, то f ( G ) в 4 C O L : просто используйте четвертый цвет для u ;G3COLf(G)4COLu
  • если в 4 C O L , то вы можете доказать , что все узлы , за исключением функции и имеют цвет , который не у «s, следовательно , G находится в 3 C O L .f(G)4COLuuG3COL

Это доказывает , что является сокращение и что 4 С О л труднее , чем 3 C O L . Вы можете доказать , точно так же , что п C O L тверже м C O L для любого п м , интересное доказательство бытия того , что 3 C O L тверже любого п C O L .f4COL3COLnCOLmCOLnm3COLnCOL

jmad
источник
Почему такое сокращение означает, что B не проще, чем A? УФ для усилий, но слишком абстрактно для моего маленького мозга.
Несчастный кот
Неужели ответ будет таким же для В, что и для А после того, как вы уменьшите А до В? Я думаю, я понял: если исходный экземпляр имеет три цвета, то преобразованный экземпляр будет иметь четыре цвета, поэтому, если ответ «да, у него есть четыре цвета», ответ также «да, он имеет три раскраски "? Но разве не возможно, что преобразованный экземпляр B имеет четырехцветную окраску, а A - трехцветную? Я думаю, что легче раскрасить график четырьмя цветами ...
The Unfun Cat
@TheUnfunCat (обновлено с 3-х и 4-х
цветным