Pytania o problemy decyzyjne, które można rozwiązać na niedeterministycznych maszynach Turinga w czasie wielomianu długości wejścia.
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 istnieją problemy NP-zupełne, które dowiodły algorytmów podwykładniczych? Proszę o ogólne informacje na temat spraw, nie mówię tutaj o przypadkach specjalnych, które można zastosować. Pod wykładniczo rozumiem porządek wzrostu powyżej wielomianów, ale mniejszy niż wykładniczy, na przykład...
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...
Mój kolega i ja właśnie uderzyliśmy w notatki jednego z naszych profesorów. Notatki stwierdzają, że istnieją zadania, które można rozwiązać w czasie wielomianowym (są w klasie PF), ale NIE są możliwe do zweryfikowania w czasie wielomianowym (NIE są w klasie NPF). Aby rozwinąć te klasy: Otrzymujemy...
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...
Wielu przyszło na myśl, że we wszystkich dowodach kompletności , które przeczytałem (które pamiętam), zawsze trywialne jest pokazanie, że problem jest w i pokazanie, że jest to -hard jest ... trudną częścią. Jakie problemy zakończone to te, których weryfikatory czasu wielomianowego są wysoce...
Chciałbym rozpocząć pytanie od stwierdzenia, że jestem programistą i nie mam dużego doświadczenia w teorii złożoności. Jedną z rzeczy, które zauważyłem, jest to, że o ile wiele problemów jest NP-zupełnych, o tyle w przypadku problemów z optymalizacją niektóre są znacznie trudniejsze do...
Rozumiem więc, że problem decyzyjny jest zdefiniowany jako Czy istnieje ścieżka P taka, że koszt jest niższy niż C? i możesz łatwo sprawdzić, czy to prawda, weryfikując otrzymaną ścieżkę. Co jednak, jeśli nie ma ścieżki, która spełniałaby te kryteria? Jak zweryfikowałbyś odpowiedź „nie”...
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 =
Twierdzenie Galois skutecznie mówi, że nie można wyrazić pierwiastków wielomianu stopnia> = 5 za pomocą racjonalnych funkcji współczynników i rodników - czy nie można tego odczytać, mówiąc, że biorąc pod uwagę wielomian, nie ma deterministycznego algorytmu znajdowania pierwiastków? Zastanówmy...
Czy przeprowadzono badania nad złożonością dowodu rozwiązania problemu P = NP? Jeśli nie, biorąc pod uwagę brak postępów w rozwiązywaniu problemu, czy nie byłoby rozsądne przypuszczać, że jakikolwiek dowód rozwiązujący problem P = NP będzie wymagał wielomianowej liczby...
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...
Widziałem z tego postu przy przepełnieniu stosu, że istnieją pewne stosunkowo szybkie algorytmy przesiewania przedziału liczb, aby sprawdzić, czy jest liczba pierwsza w tym przedziale. Czy to jednak oznacza, że ogólny problem decyzyjny: (Czy istnieje liczba pierwsza w przedziale?) Znajduje się w...
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...
Mój wykładowca wydał oświadczenie Jakikolwiek problem skończony nie może być NP-Complete Mówił wtedy o Sudoku, mówiąc coś w stylu, że dla Sudoku 8x8 istnieje skończony zestaw rozwiązań, ale nie pamiętam dokładnie, co powiedział. Zapisałem notatkę, którą zacytowałem, ale nadal nie...
Właśnie przeczytałem kilka stron w książce Sipsera Wprowadzenie do teorii obliczeń na temat problemu z korespondencją pocztową i myślę, że PCP jest w rzeczywistości w NP. Certyfikującej wynosi: dla konfiguracji wejściowej stos łączenie T 1 , T 2 , . . . , t n jako ciąg t i konkatenacja b 1 , b(...
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...
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