Будет ли экспоненциальная нижняя оценка NP-полного языка доказывать, что P не равен NP?
Если бы кто-то смог доказать экспоненциальную нижнюю оценку для NP-полной задачи, это доказало бы, что P ≠ NP?
2 ответа
Да, это доказало бы, что P не равно NP. Все полиномы ограничены сверху любой экспоненциальной функцией, поэтому экспоненциальная нижняя оценка любой задачи NP доказала бы, что проблема не в P, и, таким образом, доказала бы, что P не может быть равной NP.
Надеюсь это поможет!
Вы абсолютно правы. Если вы докажете экспоненциальную нижнюю оценку для A, вы показали, что A не может лежать в P. Если A действительно лежала в P, она была бы разрешима за полиномиальное время, которое асимптотически быстрее вашей только что доказанной нижней границы - у нас есть противоречие!
Тем не менее, вам не нужно выбирать NP-полную проблему. Вы можете выбрать любой язык А в NP. Доказав, что A не лежит в P, вы также доказали, что P не равен NP. Зачем? Потому что если бы P действительно равнялся NP, A также лежал бы в P, поскольку мы только что выбрали A из NP.