Если P = NP, почему

15

Очевидно, что если , все языки в кроме и , будут -полными.P = N P PΣ N PP=NPPΣ*Н П

Почему именно эти два языка? Разве мы не можем свести к ним какой-либо другой язык в Pп , выводя их при принятии или не принятии?

Дэвид Фокс
источник

Ответы:

25

Поскольку в нет строк , любая машина, которая его вычисляет, всегда отклоняет, поэтому мы не можем сопоставить экземпляр других проблем с Yes. Точно так же для Σ нечего сопоставлять с No-instance.Σ*

Люк Мэтисон
источник
4

Вам нужно полиномиальное сведение от задачи А к задаче B , если вы хотите , чтобы доказать , что B является «тяжелее» , чем A . Мы строим полином сокращение путем преобразования любого экземпляра х из A в экземпляр F ( х ) из B такие , что х тогда и только тогда F ( х ) B .AВВAИксAе( х )Вx Aе( x ) B

Функция f должна и может быть полиномиальной. Если Р = Н Р и проблема NP, то F сама может решить проблему А проблемы и код вставки любого х в некоторый элемент у из B и любого х в некоторый элемент г , что не находится в B .еP = N PAеAx AYВх АZВ

Если B является либо или Σ * , то у или г не может существовать, в противном случае рассуждение выше , показывает , что B сложнее , чем A .ВΣ*YZВA

jmad
источник
3

Просто примечание: предыдущие ответы в порядке, однако вы не слишком далеки от правильного тривиального сокращения:

если P = N P, то любой L N P сводится по Карпу к языку { 1 } (просто отображаем за полиномиальное время каждый x L на 1, каждый x L на 0), что является тривиально редким языкомP = N PL N P{ 1 }x LxL

Обратное направление: «если полный язык N P сводится по Карпу к разреженному множеству, то P = N P », безусловно, более интересен и известен как теорема Махани :NPP=NP

Пусть Ĉ быть постоянным и быть установлен таким образом, что для всех п , имеет в большинстве п гр строк длины п . Если является Н Р -полным , то Р = Н Р .cAnAncNAН ПP = N P

Вор
источник