Pytania otagowane jako complexity-theory

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

2
Czy redukcja karp jest identyczna z redukcją Levina
Definicja: Redukcja karp Język jest karpem redukowalnym do języka jeśli istnieje funkcja obliczalna w czasie wielomianowym tak, że dla każdego , wtedy i tylko wtedy, .AAABBBf:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f:\{0,1\}^*\rightarrow\{0,1\}^*xxxx∈Ax∈Ax\in Af(x)∈Bf(x)∈Bf(x)\in B Definicja: Redukcja Levina Problem wyszukiwania można sprowadzić do Levina do problemu wyszukiwania jeśli istnieje funkcja czasu wielomianowego której Karp redukuje do a …
2
Jaka jest złożoność problemu pustki dla dwukierunkowych DFA?
Zastanawiam się, jaka jest złożoność czasowa określania pustki dla dwukierunkowych DFA? Oznacza to, że skończone automaty mogą przesuwać się wstecz na swojej taśmie wejściowej tylko do odczytu. Według Wikipedii są one równoważne DFA, chociaż równoważny DFA może być wykładniczo większy. Znalazłem złożoność stanu dla ich uzupełnień i skrzyżowań, ale nie …
1
Jak podzielić zestaw na określoną liczbę rozłącznych podzbiorów pod pewnymi warunkami?
Dostaję zestaw , liczbę całkowitą s \ leqslant k i nieujemne liczby całkowite a_ {ij} . Mój problem polega na znalezieniu s podzbiory rozłączne S_j z \ {1, \ ldots, k \} takie, że:A≜{1,…,k}A≜{1,…,k}A\triangleq\{1,\ldots,k\}s⩽ks⩽ks\leqslant kaijaija_{ij}sssSjSjS_j{1,…,k}{1,…,k}\{1,\ldots,k\} ⋃sj=1Sj=A⋃j=1sSj=A\bigcup_{j=1}^s S_j=A ; i |Sj|⩽aij|Sj|⩽aij|S_j|\leqslant a_{ij} dla wszystkich i∈Sji∈Sji\in S_j i j=1,…,sj=1,…,sj=1,\ldots,s . Jak rozwiązać …
1
Dlaczego NP jest w EXPTIME?
Czy istnieje prosty sposób, aby dowiedzieć się, dlaczego NP jest w WYGODZIE? Wydaje mi się a priori możliwe, że może istnieć problem, który wymaga czasu nadwykładniczego do rozwiązania, ale którego rozwiązanie można zweryfikować w czasie wielomianowym.
1
Twardość NP pokrycia kawałkami prostokątnymi (Google Hash Code 2015 Round Round)
Kodeks Hash 2015 Okrągły testowania Google ( oświadczenie problemem ) poprosił o następującym problemem: dane wejściowe: siatka z zaznaczonymi kwadratami, próg , maksymalny obszarT ∈ N A ∈ NM.M.MT.∈ N.T.∈N.T \in \mathbb{N}A ∈ NZA∈N.A \in \mathbb{N} Wydajność: największa powierzchnia całkowita zestawu rozłącznych prostokątów o współrzędnych całkowitą w tak, że każdy …
1
Dlaczego ten argument za
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 ≠ …
1
Czy problem trudny dla NP może być średnio wielomianowy?
Zastanawiam się, czy są jakieś problemy twarde typu , które w przeciętnym przypadku są `` wielomianowe ''. Sądzę, że istnieją dwa sposoby interpretacji tego?N.P.N.P.NP Jeśli , czy może istnieć algorytm rozwiązujący problem twardości N P z zamortyzowanym (przypadkiem średnim) czasem pracy O ( n k ) dla stałej k ?P.≠ …
1
Dlaczego wszystkie problemy w FPTAS występują również w FPT?
Zgodnie z artykułem Wikipedii na temat schematów aproksymacji czasu wielomianowego : Wszystkie problemy w FPTAS są możliwe do rozwiązania ze stałymi parametrami. Ten wynik mnie zaskakuje - te klasy wydają się zupełnie różne od siebie. FPTAS charakteryzuje problemy na podstawie ich łatwości do przybliżenia, podczas gdy FPT charakteryzuje problemy na …
1
Średnia długość ścieżek st (prostych) na skierowanym wykresie
Biorąc pod uwagę fakt, że wyliczenie ścieżki - jest problemem # P-zupełnym, czy mogłyby istnieć wydajne metody obliczające (lub przynajmniej przybliżające) średnią długość ścieżki - bez ich wyliczania? Co jeśli ścieżki mogą ponownie odwiedzać wierzchołki?t s tssstttsssttt Pomocne mogą być również odpowiednie wyniki na specjalnych wykresach.
1
Niezależny zestaw na sześciennych grafach bez trójkątów
Wiem, że maksymalny niezależny zestaw na sześciennych grafach bez trójkątów jest NP-zupełny. Czy nadal jest NP-kompletny, jeśli potrzebujemy, aby niezależny zestaw miał dokładnie taką samą wielkość ?| V.| / 2|V.|/2)|V|/2 Zasadniczo YES wystąpienie problemu z niezależnym zestawem na szesnastkowym grafie bez trójkątów musi mieć dokładnie węzły. ŻADNA instancja nie ma …
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.