Pytania otagowane jako np

Pytania o problemy decyzyjne, które można rozwiązać na niedeterministycznych maszynach Turinga w czasie wielomianu długości wejścia.

2
Czy istnieje zadanie, które można rozwiązać w czasie wielomianowym, ale którego nie da się zweryfikować w czasie wielomianowym?
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 trochę danych wejściowych X …
3
Problemy z NP-zupełnością nie „oczywiście” w NP
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 nietrywialne?NP NP NPNPNP\textbf{NP}NPNP\textbf{NP}NPNP\textbf{NP}NPNP\textbf{NP}
3
Dlaczego problemy związane z NP są tak różne pod względem ich przybliżenia?
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 oszacowania niż inne. Dobrym przykładem jest TSP. Chociaż …
2
W jaki sposób problem sprzedawcy podróży jest weryfikowalny w czasie wielomianowym?
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” bez rozwiązania problemu z najlepszą ścieżką TSP, …
3
Czy istnieje pogląd na złożoność twierdzenia Galois?
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 się teraz nad pytaniem o formę: „Biorąc pod uwagę prawdziwy zakorzeniony …
4
Złożoność dowodu dowodu lub dowodu P = NP
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 kroków?
3
Czy jakiś skończony problem może występować w NP-Complete?
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 rozumiem. Sudoku są NP kompletne, jeśli się nie mylę. Problem …
13 np-complete  np 
1
Czy ustalenie, czy istnieje liczba pierwsza w przedziale, o którym wiadomo, że jest w P czy NP-zupełna?
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 P. (Było wiele odpowiedzi na ten post, których …
2
Czy można rozwiązać dowolny problem NP-Complete przy użyciu co najwyżej przestrzeni wielomianowej (ale przy użyciu czasu wykładniczego?)
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 ją ogólnie uogólnić na EXPTIME …
2
Czy problem korespondencyjny występuje w NP?
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 …
5
Wada mojego NP = dowód CoNP?
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 …
1
Czy to trudne NP? Nie mogę tego udowodnić.
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 …
11 graphs  np 
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 …
1
Czy kompletne zestawy NP są tworzone z dwóch innych zestawów tylko wtedy, gdy co najmniej jeden jest twardy NP?
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 z koniecznie NP-twardy? Wiem, że oba nie mogą być w P (zakładając, …
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.