Istnieje wiele prób udowodnienia albo albo P ≠ N P , i oczywiście wiele osób myśli o tym pytaniu, mając pomysły na udowodnienie obu kierunków.P = N PP=NP\mathsf{P} = \mathsf{NP} P ≠ N PP≠NP\mathsf{P} \neq \mathsf{NP} Wiem, że istnieją metody, które okazały się nieskuteczne, i prawdopodobnie jest...
Rozumiem na wysokim poziomie problem i rozumiem, że gdyby absolutnie „udowodniono”, że jest to prawdą w dostarczonym rozwiązaniu, otworzyłoby to drzwi do rozwiązania wielu problemów w dziedzinie informatyki.P=NPP=NPP=NP Moje pytanie brzmi: jeśli ktoś opublikowałby niepodważalny, konstruktywny...
Czy są jakieś znane problemy w (a nie w ), które nie są ukończone? Rozumiem, że nie ma obecnie znanych problemów, ale nie zostało to wykluczone. NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP} Jeśli występuje problem, który to (a nie ), ale nie , czy byłby to wynik braku istniejącego izomorfizmu między...
Kiedy wyjaśniłem dowód Baker-Gill-Solovay, że istnieje wyrocznia, którą możemy mieć, , oraz wyrocznia, z którą możemy otrzymać P ≠ N P przyjacielowi, pojawiło się pytanie, dlaczego takie techniki nie nadają się do udowodnienia problemu P ≠ N P i nie mogłem udzielić zadowalającej odpowiedzi.P = N...
Czy to możliwe, że a liczność jest taka sama jak liczność ? Czy też oznacza, że i muszą mieć różne liczności?P N P P ≠ N P P N PP≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not =
Jeśli faktycznie jest równe N P , w jaki sposób poprawiłoby to nasze algorytmy do szybszego obliczania liczb całkowitych. Innymi słowy, jaki wgląd dałby nam ten fakt w lepszym zrozumieniu faktoryzacji liczb całkowitych?P.P.{\sf P}N P.NP.{\sf
Jestem pewien, że ktoś pomyślał o tym wcześniej lub natychmiast go odrzucił, ale dlaczego teoria dychotomii Schaefera wraz z twierdzeniem Mahaneya o rzadkich zestawach nie implikuje P = NP? Oto moje rozumowanie: Stwórz język który jest równy SAT, przecięty nieskończonym rozstrzygalnym rzadkim...
To mój pierwszy post po tym, jak od jakiegoś czasu jestem pasywnym użytkownikiem. Chciałbym zadać kilka pytań, jeśli mogę. Nie jestem matematykiem, ale moje pytanie dotyczy matematyki / informatyki. W szczególności problem P vs NP. Wiem, że jest to problem, którego elitarni specjaliści nie byli...
Zastanawiam się nad tym w oparciu o kilka miejsc online, w których można dzwonić NP=NP=\sf NP= współ-NPNP\sf NP główny otwarty problem ... ale nie mogę znaleźć żadnego wskazania, czy jest to to samo, co P=NPP=NP\sf P=NP
Mam ten bardzo prosty „dowód” na NP = CoNP i myślę, że gdzieś coś zrobiłem źle, ale nie mogę znaleźć, co jest nie tak. Czy ktoś może mi pomóc? Niech A będzie pewnym problemem w NP, i niech M będzie decydującym dla A. Niech B będzie dopełnieniem, tj. B jest w CoNP. Ponieważ M jest decydującym,...
Zdaję sobie sprawę, że wydaje się to bardzo głupie (lub zbyt oczywiste, by stwierdzić) pytanie. Jednak w pewnym momencie jestem zdezorientowany. Możemy pokazać, że P NP=== wtedy i tylko wtedy, gdy możemy zaprojektować algorytm, który rozwiązuje dowolny przypadek problemu w NP w czasie...
To chyba głupie pytanie, ale po prostu nie rozumiem. W kolejnym pytaniu wymyślili dychotomia twierdzenia Schaefer jest . Dla mnie wygląda na to, że udowadnia, że każdy problem CSP jest w P lub NP-kompletny, ale nie pomiędzy. Skoro każdy problem NP można przekształcić w czasie wielomianowym w CSP...
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 ≠ N PP.= NP.P.=N.P.P=NPZAZAAP.ZA=...
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...
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
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ł...
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ą...
Valiant i Vazirani udowodnili, że SAT można zredukować do UNIKALNEGO SAT przy randomizowanych probabilistycznych redukcjach czasu wielomianowego. Calabro i in . pokazał, że UNIKALNY k-SAT jest tak trudny jak k-SAT. Teraz pytanie brzmi: jeśli ktoś pokaże, że UNIKALNY k-SAT jest w P, czy oznacza to,...