Pytania otagowane jako reductions

W obliczalności i złożoności, znajdowanie mapowań między problemami, które pozwalają rozwiązać jeden problem przy użyciu rozwiązania innego. Aby dowiedzieć się, jak zredukować teorię języka programowania (np. Redukcja beta), zobacz [rachunek-lambda] lub [przepisywanie terminu].

1
Redukcje wśród nierozstrzygniętych problemów
Przykro mi, jeśli na to pytanie ma jakąś trywialną odpowiedź, której mi brakuje. Ilekroć badam jakiś problem, który okazał się nierozstrzygalny, zauważam, że dowód polega na zmniejszeniu do innego problemu, który okazał się nierozstrzygalny. Rozumiem, że tworzy to pewien porządek na poziomie trudności problemu. Ale moje pytanie brzmi - czy …
2
Czy HORN-SAT w LIN, jeśli tak, to dlaczego nie oznacza to, że P = LIN?
Zoo Złożoności definiuje jako klasę problemów decyzyjnych rozwiązywanych przez deterministyczną maszynę Turinga w czasie liniowym.L IN.LINLIN L IN.⊆ P.LIN⊆PLIN \subseteq P Ponieważ HORN-SAT można rozwiązać w (jak wskazano w algorytmach czasu liniowego do testowania spełniania formuł róg zdań (1984) )O ( n )O(n)O(n) Przedstawiono nowe algorytmy decydujące o tym, czy …
2
Jeśli A mapuje się redukowalnie do B, to dopełniacz A jest mapowalny redukowalny do dopełniacza B
Studiuję do finałowej teorii obliczeń i walczę z właściwym sposobem odpowiedzi na pytanie, czy to stwierdzenie jest prawdziwe w odniesieniu do fałszu. Przez definicję z możemy skonstruować następujące oświadczenie,≤m≤m\leq_m w ∈ A⟺fa( w ) ∈ B → w ∉ A⟺fa( w ) ∉ Bw∈A⟺f(w)∈B→w∉A⟺f(w)∉Bw \in A \iff f(w) \in B …
1
Jak wyglądają klasy złożoności, jeśli zastosujemy redukcje Turinga?
Do rozumowania takich rzeczy, jak kompletność NP, zwykle stosujemy redukcje wielokrotne jeden (tj. Redukcje Karp). Prowadzi to do takich zdjęć: (zgodnie ze standardowymi przypuszczeniami). Jestem pewien, że wszyscy znamy tego rodzaju rzeczy. Jakie otrzymamy zdjęcie, jeśli będziemy pracować z redukcjami Turinga (tj. Redukcjami Cooka)? Jak zmienia się obraz? PNPPNPP^{NP}NPNPNPcoNPcoNPcoNPPNPPNPP^{NP}NPNPNP P⊂PNP⊂PH⊂PSPACEP⊂PNP⊂PH⊂PSPACEP …
2
Czy możemy skonstruować redukcję Karp z redukcji Cooka między problemami NP?
Mieliśmy kilka pytań na temat relacji redukcji Cooka i Karp . Oczywiste jest, że redukcje Cooka (redukcje Turinga w czasie wielomianowym) nie definiują tego samego pojęcia kompletności NP jak redukcje Karp (redukcje w postaci wielomianu w jednym czasie), które są zwykle stosowane. W szczególności redukcje Cooka nie mogą oddzielić NP …
2
Dla dowolnego języka istnieje takie, że ale
Próbuję wymyślić dowód na następujące kwestie: Dla każdego języka AAA istnieje język BBB , tak że A≤TBA≤TBA \le_{\mathrm{T}} B a B ≰TA≰TA\nleq_{\mathrm{T}} A . Myślałem o pozwoleniu BBB być ATMATMA_{\mathrm{TM}} , ale zdaję sobie sprawę, że nie wszystkie języki Turing można zredukować do ATMATMA_{\mathrm{TM}} , więc A≤TBA≤TBA \le _T B …
2
Ograniczenie maksymalnego przepływu do dopasowania dwustronnego?
Istnieje słynna i elegancka redukcja od maksymalnego problemu dwustronnego dopasowania do problemu maksymalnego przepływu: tworzymy sieć z węzłem źródłowym , węzłem końcowym i jednym węzłem dla każdego elementu, który ma być dopasowany, a następnie dodajemy odpowiednie krawędzie.sssttt Z pewnością istnieje sposób na ograniczenie maksymalnego przepływu do maksymalnego dopasowania dwustronnego w …
1
Twardość i kierunki redukcji
Powiedzmy, że wiemy, że problem A jest trudny, a następnie redukujemy A do nieznanego problemu B, aby udowodnić, że B jest również trudny. Jako przykład: wiemy, że 3-kolorowanie jest trudne. Następnie redukujemy kolorowanie 3 do koloru 4. Po połączeniu jednego z kolorów 3-kolorowania masz 4-kolory, ergo 4-kolory są trudne. Właśnie …
2
Maszyna Turinga z nieskończonym alfabetem
Czy maszyna Turinga, która może odczytywać i zapisywać symbole z nieskończonego alfabetu, ma większą moc niż zwykła TM (to jedyna różnica, maszyna wciąż ma skończoną liczbę stanów)? Intuicja mówi mi, że nie, ponieważ potrzebujesz nieskończonej liczby stanów, aby odróżnić każdy symbol. Myślę więc, że niektóre symbole lub przejścia spowodowane przez …
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.