Pytania otagowane jako p-vs-np

1
Dlaczego ten argument za
Wiem, że to głupie, ale udało mi się pomylić i potrzebuję pomocy w rozwiązaniu tego Załóżmy, że , więc wyraźnie dla każdej wyroczni mamy co zaprzecza faktowi, że istnieje pewna wyrocznia dla której , stądA P A = N P A A P A ≠ N P A P ≠ …
2
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 . …
1
Jeśli
Jeśli P.=NPP=NP\mathbf{P} = \mathbf{NP} , to czy L =NLL=NL.\mathbf{L} = \mathbf{NL} ? Zadaję to pytanie, ponieważ dla innych niedeterministycznych klas wydaje się, że P = N PP=NP.\mathbf{P} = \mathbf{NP} zawsze ustala, że ​​są one równe ich deterministycznym odpowiednikom.
4
Ewolucja sztucznych sieci neuronowych do rozwiązywania problemów NP
Niedawno przeczytałem naprawdę ciekawy wpis na blogu Google Research Blog o sieci neuronowej. Zasadniczo wykorzystują te sieci neuronowe do rozwiązywania różnych problemów, takich jak rozpoznawanie obrazów. Używają algorytmów genetycznych do „ewolucji” ciężarów aksonów. Więc w zasadzie mój pomysł jest następujący. Gdybym miał napisać program, który rozpoznaje liczby, nie wiedziałbym, jak …
3
Dowód, że jeżeli
Naprawdę chciałbym, abyś pomógł mi udowodnić, co następuje. Jeżeli N T i m e ( n100)⊆DTime(n1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000}) , a następnie P=NPP=NP\mathrm{P}=\mathrm{NP} . Tutaj NTime(n100)NTime(n100)\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 …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.