Dowód, że jeżeli

Naprawdę chciałbym, abyś pomógł mi udowodnić, co następuje.

Jeżeli $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ , a następnie $\mathrm{P}=\mathrm{NP}$ .

Tutaj $\mathrm{NTime}(n^{100})$ jest klasą wszystkich języków, o których decyduje niedeterministyczna maszyna Turinga w czasie wielomianowym i jest klasą wszystkich języków, o których decyduje deterministyczna maszyna Turinga w czasie wielomianowym .$O(n^{100})$O ( n 1000$\mathrm{DTime}(n^{1000})$$O(n^{1000})$

Jakaś pomoc / sugestie?

Oto rozwiązanie wykorzystujące padding. Załóżmy, że . Zdefiniuj nowy język . Każde odpowiada niektórym długości . Dlatego możemy zdecydować, czy w niedeterministycznym czasie , tj. . Aby zdecydować, czy , utwórz i uruchom -czasowy algorytm deterministyczny dlaL ′ = { x 0 | x | 10 - | x | : x ∈ L } x ∈ L y ∈ L ′ | y | = | x | + ( | x | 10 - | x | ) = $L \in \mathrm{NTime}(n^{1000})$$L' = \{x0^{|x|^{10}-|x|} : x \in L\}$$x \in L$$y \in L'$ lat ∈ L ′ | x | 1000 = | y | 100 L ′ ∈ N T i m e ( n 100 ) ⊆ D T i m e ( n 1000 ) x ∈ L y = x 0 x 10 - | x | | y | 1000 = | x | $|y| = |x| + (|x|^{10}-|x|) = |x|^{10}$$y \in L'$$|x|^{1000} = |y|^{100}$$L' \in \mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$$x \in L$$y = x0^{x^{10}-|x|}$$|y|^{1000} = |x|^{10000}$$L'$. Wnioskujemy, że .$L \in \mathrm{DTime}(n^{10000})$

Podziel problem na dwie części:

1. Jest -Complete Język N T i m e ( n 1000 ) .$\mathsf{NP}$$\mathsf{NTime}(n^{1000})$
2. Jeżeli -Complete język jest D , T i m e ( n 1000 ) ⊂ P wówczas P = N P .$\mathsf{NP}$$\mathsf{DTime}(n^{1000}) \subset \mathsf{P}$$\mathsf{P}=\mathsf{NP}$

Jest to prawie banalna konsekwencja definicji kompletności NP. Jeśli jakikolwiek język w NP może być rozwiązany w czasie wielomianowym (co jest potwierdzone przez przesłankę), to wszystkie one są. Innym sposobem na przyjrzenie się temu jest przyjrzenie się twierdzeniu Cooka o kompletności NP, która redukuje wszystkie języki NP-kompletne do rozpoznania języka obejmującego SAT i konwersji niedeterministycznej maszyny Turinga w SAT.