Противоречие для неравенства P и NP?

10

Я пытаюсь утверждать, что N не равен NP, используя теоремы иерархии. Это мой аргумент, но когда я показал его нашему учителю и после дедукции, он сказал, что это проблематично, когда я не могу найти вескую причину для принятия.

Мы начнем, предполагая , что P=NP . Тогда из этого следует, что SATP что само по себе следует из того, что SATTIME(nk) . Как стенды, мы можем сделать уменьшить каждый язык в NP к SAT . Следовательно, NPTIME(nk) . Напротив, теорема иерархии времени утверждает, что должен быть языкATIME(nk+1) , которого нет вTIME(nk) . Это привело бы нас к выводу, чтоA находится вP , а не вNP , что противоречит нашему первому предположению. Таким образом, мы пришли к выводучтоPNP .

Что-то не так с моим доказательством?

inverted_index
источник
2
Пожалуйста, напишите что-нибудь вроде $\mathit{SAT}$вместо $SAT$. Как писал Лесли Лэмпорт в своей оригинальной книге LaTeX, последняя означает S раз A раз T.
Олифонт - восстановить Монику
А еще лучше используйте complexityпакет и просто напишите \SAT. (Я думаю, что это не доступно в этом стеке, хотя.)
Олифаунт - восстановить Монику
@Oliphaunt Почему бы не предложить редактирование, когда вы можете улучшить сообщение? Хотя я должен сказать, что здесь разница (если есть) намного тоньше, чем я ожидал.
Дискретная ящерица
1
@Discretelizard Я часто делаю, но на этот раз это было "слишком много работы" (я был / я на мобильном телефоне). Ввод всех этих $ и \ является привередливой работой. Я выбрал для обучения вместо. (Это решение, возможно, не было полностью рациональным.)
Олифонт - восстановить Монику

Ответы:

55

Тогда из этого следует, что SATP что само по себе следует из того, что SATTIME(nk) .

Конечно.

Как стенды, мы можем сделать уменьшить каждый язык в NP к SAT . Следовательно, NPTIME(nk) .

Нет. Полиномиальное сокращение времени не бесплатно. Можно сказать, что требуется время O(nr(L)) чтобы привести язык L к SAT , где r(L) - показатель степени в использованном сокращении времени за полином. Это где ваш аргумент разваливается. Не существует конечного k такого, что для всех LNP имеем r(L)<k . По крайней мере, это не следует из P=NP и было бы гораздо более сильным утверждением.

И это более сильное утверждение делает действительно конфликт с теоремой иерархии времени, которое говорит нам , что P не может разрушиться в TIME(nk) , не говоря уже о всех NP .

orlp
источник
1
Это не только время для самого сокращения. Вы можете уменьшить проблему. Если я могу решить X в O (n ^ 5), и я могу свести проблему в Y в O (n ^ 6) к экземпляру X размером O (n ^ 3), то мне нужно O (n ^ 15) в целом.
gnasher729
Забавно, что этот аргумент применим и к задачам, полным PTIME, например, HORNSAT, который решаем за линейное время (но не все задачи в P являются линейным временем).
Коди
8

Suppose that 3SATNTIME[nk]. By the nondeterministic version of the time hierarchy theorem, for any r, there is a problem XrNTIME[nr] that is not in NTIME[nr1]. This is an unconditional result that doesn't depend on any kind of assumption such as PNP

Выберите любой r>k . Предположим, что мы имеем детерминированное сокращение от Xr до 3SAT которое выполняется за время  nt . Он создает экземпляр размером 3SAT не более  nt , который может быть решен за время не более (nt)k=ntk . По нашему выбору  Xr , мы должны иметь tk>r1 , поэтому t>(r+1)/k . Эта функция растет без связи с r .

Не Это означает , что там не связаны о том , как долго он может сделать , чтобы уменьшить произвольное NP задачу 3SAT . Даже если 3SATP , все еще нет предела тому, как долго эти сокращения могут занять. Так, в частности, даже если 3SATDTIME[nk] для некоторого  k , мы не можем заключить, что NPDTIME[nk]NPDTIME[nk]k>k

Дэвид Ричерби
источник