211
правок
Изменения
м
Нет описания правки
<tex>2^n(1-\frac1{r+1})^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [http://ru.wikipedia.org/wiki/Ряд_Тейлора#.D0.A0.D1.8F.D0.B4.D1.8B_.D0.9C.D0.B0.D0.BA.D0.BB.D0.BE.D1.80.D0.B5.D0.BD.D0.B0_.D0.BD.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9 формулой Тейлора] для логарифма).
Таким образом, мы можем разрешить язык <tex>\mathrm{LSAT}</tex> за полиномиальное время, найдя лексиграфически лексикографически минимальную строку, удовлетворяющую формулу, и сравнив её с нашим аргументом. Так как <tex>\mathrm{LSAT}\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.
}}
