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?

complexity-theory time-complexity p-vs-np

— inverted_index
źródło

Proszę napisać coś takiego $\mathit{SAT}$ zamiast $SAT$ . Jak napisał Leslie Lamport w swojej oryginalnej książce LaTeX, ta ostatnia oznacza S razy A razy T.

— Oliphaunt - przywraca Monikę

Jeszcze lepiej, użyj complexitypakietu i po prostu napisz \SAT. (Myślę, że to nie jest dostępne na tym stosie.)

— Oliphaunt - przywróć Monikę

@Oliphaunt Dlaczego nie zaproponować edycji, kiedy możesz poprawić post? Chociaż muszę powiedzieć, że tutaj różnica (jeśli w ogóle) jest o wiele bardziej subtelna, niż się spodziewałam.

— Dyskretna jaszczurka

@Discretelizard Często to robię, ale tym razem było to „za dużo pracy” (byłem na telefonie). Wprowadzenie wszystkich tych $ i \ jest wybredną pracą. Zamiast tego wybrałem edukację. (Ta decyzja mogła nie być całkowicie racjonalna).

— Oliphaunt - przywróć Monikę

Odpowiedzi:

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 do zajmuje czas $O(n^{r(L)})$ , gdzie jest wykładnikiem stosowanej wielomianowej redukcji czasu. Tu rozpada się twój argument. Nie ma skończonego takiego, że dla wszystkich mamy . Przynajmniej nie wynika to z $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$ .

— orlp
źródło

To nie tylko czas na samą redukcję. Możesz zredukować do większego problemu. Jeśli mogę rozwiązać X w O (n ^ 5) i mogę zredukować problem w Y w O (n ^ 6) do wystąpienia X o rozmiarze O (n ^ 3), to potrzebuję O (n ^ 15) w całości.

— gnasher729

Zabawnie, ten argument dotyczy również problemów związanych z PTIME, np. HORNSAT, który można rozwiązać w czasie liniowym (ale nie wszystkie problemy w P są czasem liniowym).

— cody

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'$ .

— David Richerby
źródło