Dowód sprzeczności dla nierówności P i NP?

Próbuję argumentować, że N nie jest równe NP przy użyciu twierdzeń hierarchicznych. To mój argument, ale kiedy pokazałem go naszemu nauczycielowi i po dedukcji powiedział, że jest to problematyczne, gdy nie mogę znaleźć ważnego powodu do zaakceptowania.

Zaczynamy od założenia, że . Następnie zwraca który następnie następuje po tym . Na obecnym etapie jesteśmy w stanie zredukować każdy język w do . Dlatego . Przeciwnie, twierdzenie o hierarchii czasu stwierdza, że ​​powinien istnieć język , który nie jest w . Doprowadziłoby to nas do wniosku, że jest w , a nie w , co jest sprzeczne z naszym pierwszym założeniem. Doszliśmy więc do wniosku, że .$P=NP$$\mathit{SAT} \in P$$\mathit{SAT} \in TIME(n^k)$$NP$$\mathit{SAT}$$NP \subseteq TIME(n^k)$$A \in TIME(n^{k+1})$$TIME(n^k)$$A$$P$$NP$$P \neq NP$

Czy coś jest nie tak z moim dowodem?

Następnie daje $SAT \in P$ który sam następnie podąża za $SAT \in TIME(n^k)$ .

Pewnie.

Jako trybun, jesteśmy w stanie wykonać każde zmniejszenie język w $NP$ do $SAT$ . Dlatego $NP \subseteq TIME(n^k)$ .

Nie. Wielomianowe skrócenie czasu nie jest bezpłatne. Można powiedzieć, że redukcja języka L do S A T zajmuje czas $O(n^{r(L)})$ , gdzie r ( L ) jest wykładnikiem stosowanej wielomianowej redukcji czasu. Tu rozpada się twój argument. Nie ma skończonego k takiego, że dla wszystkich L ∈ N P mamy r ( L ) < k . Przynajmniej nie wynika to z P = N P$L$$SAT$$r(L)$$k$$L \in NP$$r(L) < k$$P = NP$ i byłoby znacznie silniejszym stwierdzeniem.

I to rzeczywiście robi mocniejsze stwierdzenie sprzeczności z twierdzeniem hierarchii czasowej, która mówi nam, że $P$ nie może zapaść w $TIME(n^k)$ , nie mówiąc już o wszystkich $NP$ .

Załóżmy, że $\mathrm{3SAT}\in\mathrm{NTIME}[n^k]$ . Według niedeterministycznej wersji twierdzenia o hierarchii czasu dla dowolnego  $r$ istnieje problem $X_r\in\mathrm{NTIME}[n^r]$ którego nie ma w $\mathrm{NTIME}[n^{r-1}]$ . Jest to bezwarunkowy wynik, który nie zależy od żadnego rodzaju założeń, takich jak $\mathrm{P}\neq\mathrm{NP}$

Wybierz dowolny $r>k$ . Załóżmy, że mamy deterministyczną redukcję z $X_r$ do $\mathrm{3SAT}$ która biegnie w czasie  $n^t$ . Wytwarza instancję wielkości $\mathrm{3SAT}$ o wielkości co najwyżej  $n^t$ , którą można rozwiązać w czasie co najwyżej $(n^t)^k=n^{tk}$ . Wybierając  $X_r$ , musimy mieć $tk>r-1$ , więc $t>(r+1)/k$ . Ta funkcja rośnie bez ograniczeń za pomocą $r$ .

Oznacza to, że nie jest związany, jak długo może się zmniejszyć dowolny $\mathrm{NP}$ problem $\mathrm{3SAT}$ . Nawet jeśli $\mathrm{3SAT}\in \mathrm{P}$ , nadal nie ma ograniczenia, jak długo mogą potrwać te redukcje. Zatem w szczególności, nawet jeśli $\mathrm{3SAT}\in\mathrm{DTIME}[n^{k'}]$ dla niektórych  $k'$ , nie możemy stwierdzić, że $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k'}]$, a nawet$\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k''}]$dla niektórych$k''>k'$.