Мне очень нужна ваша помощь в доказательстве следующего.
Если то . P = N P
Здесь - это класс всех языков, которые могут быть определены недетерминированной машиной Тьюринга за полиномиальное время и - это класс всех языков, которые могут быть определены детерминированной машиной Тьюринга за полиномиальное время .O ( n 100 ) D T i m e ( n 1000 ) O ( n 1000 )
Любая помощь / предложения?
Ответы:
Вот решение с использованием отступов. Предположим, что . Определите новый язык . Каждому соответствует некоторый длины . Поэтому мы можем решить, будет ли в недетерминированное время , то есть . Чтобы решить, будет ли , сформировать и запустить детерминистский алгоритм | времениL ′ = { x 0 | х | 10 - | х | : x ∈ L } x ∈ L y ∈ L ′ | у | = | х | + ( | x | 10 - | x | ) = | х | 10 летL∈NTime(n1000) L′={x0|x|10−|x|:x∈L} x∈L y∈L′ |y|=|x|+(|x|10−|x|)=|x|10 | х | 1000 = | у | 100 L ′ ∈ N T i m e ( n 100 ) ⊆ D T i m ey∈L′ |x|1000=|y|100 x ∈ L y = x 0 x 10 - | х | | у | 1000 = | х | 10000 L ′ L ∈L′∈NTime(n100)⊆DTime(n1000) x∈L y=x0x10−|x| |y|1000=|x|10000 L′ , Мы заключаем, что .L∈DTime(n10000)
источник
Разбейте проблему на две части:
источник
Это почти тривиальное следствие определения NP-полноты. Если какой-либо язык в NP разрешим за полиномиальное время (что утверждается предпосылкой), то все они. Еще один способ взглянуть на это - взглянуть на теорему Кука о NP-полноте, которая сводит все NP-завершенные языки к распознаванию языка, включающего SAT, и преобразованию недетерминированной машины Тьюринга в SAT.
источник