Я пытаюсь утверждать, что N не равен NP, используя теоремы иерархии. Это мой аргумент, но когда я показал его нашему учителю и после дедукции, он сказал, что это проблематично, когда я не могу найти вескую причину для принятия.
Мы начнем, предполагая , что . Тогда из этого следует, что что само по себе следует из того, что . Как стенды, мы можем сделать уменьшить каждый язык в к . Следовательно, . Напротив, теорема иерархии времени утверждает, что должен быть язык , которого нет в . Это привело бы нас к выводу, что находится в , а не в , что противоречит нашему первому предположению. Таким образом, мы пришли к выводучто .
Что-то не так с моим доказательством?
complexity-theory
time-complexity
p-vs-np
inverted_index
источник
источник
$\mathit{SAT}$
вместо$SAT$
. Как писал Лесли Лэмпорт в своей оригинальной книге LaTeX, последняя означает S раз A раз T.complexity
пакет и просто напишите\SAT
. (Я думаю, что это не доступно в этом стеке, хотя.)Ответы:
Конечно.
Нет. Полиномиальное сокращение времени не бесплатно. Можно сказать, что требуется времяO(nr(L)) чтобы привести язык L к SAT , где r(L) - показатель степени в использованном сокращении времени за полином. Это где ваш аргумент разваливается. Не существует конечного k такого, что для всех L∈NP имеем r(L)<k . По крайней мере, это не следует из P=NP и было бы гораздо более сильным утверждением.
И это более сильное утверждение делает действительно конфликт с теоремой иерархии времени, которое говорит нам , чтоP не может разрушиться в TIME(nk) , не говоря уже о всех NP .
источник
Suppose that3SAT∈NTIME[nk] . By the nondeterministic version of the time hierarchy theorem, for any r , there is a problem Xr∈NTIME[nr] that is not in NTIME[nr−1] . This is an unconditional result that doesn't depend on any kind of assumption such as P≠NP
Выберите любойr>k . Предположим, что мы имеем детерминированное сокращение от Xr до 3SAT которое выполняется за время nt . Он создает экземпляр размером 3SAT не более nt , который может быть решен за время не более (nt)k=ntk . По нашему выбору Xr , мы должны иметь tk>r−1 , поэтому t>(r+1)/k . Эта функция растет без связи с r .
Не Это означает , что там не связаны о том , как долго он может сделать , чтобы уменьшить произвольноеNP задачу 3SAT . Даже если 3SAT∈P , все еще нет предела тому, как долго эти сокращения могут занять. Так, в частности, даже если 3SAT∈DTIME[nk′] для некоторого k′ , мы не можем заключить, что NP⊆DTIME[nk′] NP⊆DTIME[nk′′] k′′>k′
источник