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,...
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
Czytam o NPC i jego związku z PSPACE i chcę wiedzieć, czy problemy NPC można rozwiązać w sposób deterministyczny za pomocą algorytmu o najgorszym przypadku wymaganej przestrzeni wielomianowej, ale potencjalnie zajmującego wykładniczy czas (2 ^ P (n), gdzie P jest wielomianem). Co więcej, czy można...
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=...
Mam problem i myślę, że jest to trudny NP, ale nie mogę tego udowodnić. Oto wykres warstw, w którym warstwa 0 jest najwyższą warstwą, a warstwa L najniższą. istnieje pewna ukierunkowana krawędź między warstwami, gdzie krawędź (A, B) wskazuje, że węzeł A może [pokrywać] węzeł B. A kiedy A może...
Biorę kurs na złożoność obliczeniową. Mój problem polega na tym, że nie rozumiem metody relatywizacji . Próbowałem znaleźć odrobinę intuicji w wielu podręcznikach, jak dotąd niestety bez powodzenia. Będę wdzięczny, jeśli ktoś może rzucić światło na ten temat, abym mógł kontynuować sam. Kilka...
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ą...
To pytanie jest nieco odwrotne do poprzedniego pytania dotyczącego zestawów utworzonych z operacji na zestawach na zestawach NP-complete: Jeśli zbiór wynikający ze związku, przecięcia lub iloczynu kartezjańskiego dwóch rozstrzygalnych zbiorów L1L1L_1 i jest NP-kompletny, to czy przynajmniej jeden...
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ł...
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
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...
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,...