Pytania otagowane jako complexity-theory

Pytania związane z (obliczeniową) złożonością rozwiązywania problemów

5
P-Kompletność i obliczenia równoległe
Niedawno czytałem o algorytmach sprawdzania podobieństwa i czytałem, że problem jest P-zupełny . Co więcej, konsekwencją tego jest to, że ten problem lub jakikolwiek problem P-zupełny prawdopodobnie nie będzie miał wydajnych algorytmów równoległych. Jaka jest intuicja stojąca za tym ostatnim stwierdzeniem?
2
Dowód kompletności NP problemu z drzewem opinającym
Szukam wskazówek w pytaniu zadanym przez mojego instruktora. Właśnie dlatego doszedłem do wniosku, że problemem decyzyjnym jest :NP-completeNP-complete\sf{NP\text{-}complete} Na wykresie znajduje się drzewo rozpinające w G, które zawiera dokładny zestaw S = { x 1 , x 2 , … , x n } jako liście. I zdobione można wykazać, …
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ż …
1
Naturalni kandydaci do hierarchii wewnątrz NPI
Załóżmy, że . to klasa problemów w które nie są ani w ani w -hard. Listę problemów, które mogą być tutaj .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Twierdzenie Ladnera mówi nam, że jeśli wówczas istnieje nieskończona hierarchia problemów , tzn. Istnieją problemy , które są trudniejsze niż inne problemy.N P I N P …
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, …
4
Klasy złożoności, w których
Jedną z możliwych motywacji do badania klas złożoności obliczeniowej jest zrozumienie mocy różnych rodzajów zasobów obliczeniowych (losowość, niedeterminizm, efekty kwantowe itp.). Jeśli spojrzymy na to z tej perspektywy, wydaje się, że możemy uzyskać jeden wiarygodny aksjomat dla każdej próby scharakteryzowania, które obliczenia są wykonalne w pewnym modelu: Każde wykonalne obliczenie …
2
Znajdowanie co najmniej dwóch ścieżek o tej samej długości na ukierunkowanym wykresie
Załóżmy, że mamy skierowany wykres i dwa węzły A i B . Chciałbym wiedzieć, czy istnieją już algorytmy do obliczania następującego problemu decyzyjnego:G = ( V, E)G=(V,E)G=(V,E)ZAAAbBB Czy istnieją co najmniej dwie ścieżki między i B o tej samej długości?ZAAAbBB Co powiesz na złożoność? Czy mogę to rozwiązać w czasie …
1
Klasyfikacja trudnych do rozwiązania / możliwych do rozwiązania wariantów problemu satysfakcji
Ostatnio znalazłem w artykule [1] specjalną symetryczną wersję SAT o nazwie 2/2/4-SAT . Ale istnieje wiele wariantów kompletnych , na przykład: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...NPNP\text{NP} Możliwe są inne warianty: - SAT , Planar-NAE- SAT , ...222SATSAT\text{SAT}SATSAT\text{SAT} Czy istnieją artykuły ankietowe (lub strony internetowe), które klasyfikują wszystkie (dziwne) …
1
Złożoność wież Hanoi
Wpadłem w następujące wątpliwości co do złożoności Towers of Hanoi , co do których chciałbym waszych komentarzy. Czy to jest w NP? Próba odpowiedzi: Załóżmy, że Peggy (przysłowie) rozwiązuje problem i przekazuje go Victorowi (weryfikatorowi). Victor łatwo widzi, że końcowy stan rozwiązania jest właściwy (w czasie liniowym), ale nie będzie …
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.