Допустим, мы знаем, что проблема A сложная, затем мы сводим A к неизвестной проблеме B, чтобы доказать, что B также сложно.
В качестве примера: мы знаем, что 3-окраска сложна. Затем мы уменьшаем 3-окраску до 4-окраски. Сочетая один из цветов в 3-х раскрасках, вы получаете 4-х раскраски, поэтому эрго-4-раскраски трудны.
Вот как. Но почему это доказательство того, что 4-раскраска сложна? Это то, что вы можете использовать решение проблемы 4-окраски, чтобы решить проблему 3-окраски? Если так, то как? Если нет, то почему это действительное доказательство?
Бонус q: Должны ли полиномиальные сокращения идти в обоих направлениях?
Изменить: если вы сможете объяснить, почему это так, на примере вы сделаете Интернет одолжение. Я не мог найти это объяснено конкретным способом нигде.
источник
Ответы:
Сокращение от проблемы к другой проблеме B является преобразованием f любого экземпляра a из A в экземпляр f ( a ) из B , так чтоA B f a A f(a) B
Если - преобразование, сохраняющее интересующую вас сложность (например, f - это полиномиальное преобразование, если вы рассматриваете N P -твердость), то существование алгоритма A B, решающего B, подразумевает существование алгоритма, решающего A : этого достаточно для запустить п , то Б .f f NP AB B A f AB
Следовательно, существование такого уменьшения в от до B означает , что B не легче , чем A . Нет необходимости в сокращении другого пути.A B B A
Например, для раскраски графа. Вы можете уменьшить 3 цвета до 4 цветов, но не сразу. Если вы возьмете граф и выберете f ( G ) = G, то у вас будет x ∈ 3 C O L ⇒ f ( x ) ∈ 4 C O L, но у вас нет f ( x ) ∈ 4 C O L ⇒ x ∈ 3 C O L, конечно. Вывод состоит в том, что эквивалентность (G f(G)=G x∈3COL ⇒ f(x)∈4COL f(x)∈4COL ⇒ x∈3COL не соблюдается, поэтому е являетсянесокращение.(E) f
Вы можете построить правильное сокращение от 3 C O L до 4 C O L, но это немного сложнее: для любого графа G пусть f ( G ) будет графом G, расширенным другим узлом u , связанным с ребром к каждому другому узлу.f 3COL 4COL G f(G) G u
Это доказывает , что является сокращение и что 4 С О л труднее , чем 3 C O L . Вы можете доказать , точно так же , что п C O L тверже м C O L для любого п ≥ м , интересное доказательство бытия того , что 3 C O L тверже любого п C O L .f 4COL 3COL nCOL mCOL n≥m 3COL nCOL
источник