Редактирование: Теорема Махэни

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 50: Строка 50:
 
Так как <tex>S\in \mathrm{NPC}</tex> и <tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \varphi, y \rangle \in \mathrm{LSAT} \Leftrightarrow f(\langle \varphi, y \rangle) \in S</tex>.
 
Так как <tex>S\in \mathrm{NPC}</tex> и <tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \varphi, y \rangle \in \mathrm{LSAT} \Leftrightarrow f(\langle \varphi, y \rangle) \in S</tex>.
  
Так как функция <tex>f</tex> работает полиномиальное время, то <tex>f(\langle\varphi,y\rangle) \leqslant q(|\varphi|)</tex>, где <tex>q</tex> — полином.
+
Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\varphi|\geqslant|y|</tex> (<tex>|y|</tex> — длина вектора <tex>y</tex>), то <tex>f(\langle\varphi,y\rangle) \leqslant q(|\varphi|)</tex>, где <tex>q</tex> — полином.
 
<tex>S\in \mathrm{SPARSE}</tex>, следовательно <tex>\forall n \; |S \cap \Sigma^n|\leqslant p(n)</tex>, где <tex>p</tex> — некоторый полином.  
 
<tex>S\in \mathrm{SPARSE}</tex>, следовательно <tex>\forall n \; |S \cap \Sigma^n|\leqslant p(n)</tex>, где <tex>p</tex> — некоторый полином.  
  
Строка 74: Строка 74:
 
Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n\left(1-\dfrac1{r+1}\right)^k</tex> строк. Оценим <tex>k</tex>.
 
Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n\left(1-\dfrac1{r+1}\right)^k</tex> строк. Оценим <tex>k</tex>.
  
Нам нужно, чтобы <tex>2^n\left(1-\dfrac1{r+1}\right)^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [[Формула Тейлора для произвольной функции | формулой Тейлора]] для логарифма).  
+
<tex>2^n\left(1-\dfrac1{r+1}\right)^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [[Формула Тейлора для произвольной функции | формулой Тейлора]] для логарифма).  
  
 
Таким образом, мы можем разрешить язык <tex>\mathrm{LSAT}</tex> за полиномиальное время, найдя лексикографически минимальную строку, удовлетворяющую формуле, и сравнив её с нашим аргументом. Так как <tex>\mathrm{LSAT}\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.
 
Таким образом, мы можем разрешить язык <tex>\mathrm{LSAT}</tex> за полиномиальное время, найдя лексикографически минимальную строку, удовлетворяющую формуле, и сравнив её с нашим аргументом. Так как <tex>\mathrm{LSAT}\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)