Изменения
Нет описания правки
Теорема Махэни, доказанная Стефаном Махэни в 1982 году, утверждает, что если хотя бы один [[#Sparse|редкий язык]] {{---}} [[Сведение_относительно_класса_функций._Сведение_по_Карпу._Трудные_и_полные_задачи#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F_.D1.82.D1.80.D1.83.D0.B4.D0.BD.D1.8B.D1.85_.D0.B8_.D0.BF.D0.BE.D0.BB.D0.BD.D1.8B.D1.85_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87 | <tex> \mathrm{NP} </tex>{{---}}полный ]], то <tex> \mathrm{P} = \mathrm{NP} </tex>
==Подготовка к доказательству==
Это множество, называется множеством редких языков потому, что строк длины <tex> n </tex> всего <tex> 2^{n} </tex>, и если язык содержит только полином от этого числа, то при большом <tex> n </tex> эта часть стремится к нулю.
'''Пример:''' Согласно [https://en[Машина_Тьюринга#.D0.9C.D0.BD.D0.BE.D0.B3.D0.BE.D0.BB.D0.B5.D0.BD.D1.82.D0.BE.D1.87.D0.BD.D0.B0.D1.8F_.D0.BC.D0.B0.D1.88.D0.B8.D0.BD.D0.B0_.D0.A2.D1.8C.D1.8E.wikipediaD1.org/wiki/Church%E2%80%93Turing_thesis .D0.B8.D0.BD.D0.B3.D0.B0 | тезису Чёрча {{- --}} Тьюринга]], существует биекция между машинами Тьюринга и программами. Зафиксировав алфавит, можно занумеровать программы (программа будет иметь номер <tex>n</tex>, если ее код {{---}} <tex>n</tex>{{---}}е слово среди всех слов над алфавитом, отсортированных сначала по возрастанию длины, а при равной длине {{-- -}} в лексикографическом порядке), а следовательно и машины Тьюринга. Рассмотрим язык <tex> \{1^{n} \mid n</tex>{{---}}я [[Машина Тьюринга | машина Тьюринга]] останавливается в допускающем состоянии <tex> \} </tex>. Просто приняв <tex> p(n) = 1 </tex>, получим, что он принадлежит <tex> \mathrm{SPARSE}</tex>. Более того, любой унарный язык принадлежит <tex>\mathrm{SPARSE} </tex> .
==Теорема==
В обоих случаях мы сузили область поиска как минимум на <tex>\dfrac 1{r+1}</tex> её размера.
Будем повторять эту процедуру до тех пор, пока не останется не более <tex>r+1</tex> строки, которые мы можем проверить за полиномиальное время. Если какая{{---}}то из них удовлетворила формуле <tex>\varphi</tex>, то <tex>x=\min(w_i), w_i</tex> удовлетворяет <tex>\varphi</tex>. Иначе, <tex>x</tex> не существует.
Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n\left(1-\dfrac1{r+1}\right)^k</tex> строк. Оценим <tex>k</tex>.
[[Категория: Теория сложности]]
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
[[Категория: Классы P и NP, NP{{---}}полнота]]
