Z uwagi na skierowany wykres , a dwa wierzchołki s , t ∈ V . Para prostych ścieżek p 1 , p 2 od s do t jest rozłącznymi krawędziami, jeśli nie dzielą krawędzi.G = ( V, E)G=(V,E)G = (V,E)s , t ∈ V.s,t∈Vs,t \in Vp1, p2)p1,p2p_1,p_2sssttt Za pomocą maksymalnego przepływu łatwo jest zdecydować, czy...
Monotoniczna formuła CNF z m terminami na n zmiennych ( ) jest formułą postaci , gdzie każdy jest OR pewnego podzbioru zmiennych i i wynosi od 1 do m . f ( x 1 , … , x n ) = ⋀ C i C i x 1 , … , x n i 1 mx1,…,xnx1,…,xnx_1,\ldots,x_nf(x1,…,xn)=⋀Cif(x1,…,xn)=⋀Cif(x_1,\ldots,x_n) = \bigwedge...
Czytam doskonały papier ankietowy Watrous na papierze na temat teorii złożoności kwantowej. Stwierdza w nim, że byłoby zaskakujące, gdyby okazało się, że problem z QMA miałby pustą obietnicę (tj. Być językiem). Dlaczego tak jest? Czy ma to związek z faktem, że k-lokalny problem hamiltonowski jest...
Biorąc pod uwagę mieszany wykres z krawędziami i łukami , znajdź dopasowanie w które minimalizuje liczbę łuków w , gdzie jest uzyskiwane z przez kurczenie dopasowanych wierzchołków i usuwanie łuki równoległe.E A E G / M G / M GG = ( V, E, A )G=(V,E,A)G=(V,E,A)miEEZAAAmiEEG / MG/MG/MG /...
Załóżmy, że jest językiem boolowskim o skończonych łańcuchach ponad . Niech będzie liczbą łańcuchów w o długości . Dla funkcji od dodatnich liczb całkowitych do dodatnich liczb rzeczywistych, ma górną gęstość jeśli dla wszystkich wystarczająco dużych .L.L.LL n L n d ( n ) L d ( n ) L n ≤ 2 n d ( n...
Język jest w klasie iff istnieją dwa języki L1 \ w NP i L2 \ w coNP, tak że L = L1 \ cap L2D P L 1 ∈ N P L 2 ∈ c o N P L = L 1 ∩ L 2LLLDPDPDPL1∈NPL1∈NPL1 \in NPL2∈coNPL2∈coNPL2 \in coNPL=L1∩L2L=L1∩L2L = L1 \cap L2 Kanonicznym problemem z dopełnieniem DPDPDP jest SAT-UNSAT: biorąc pod uwagę dwa...
Kontekst: Rozważamy tylko digrafy. Niech CYKL będzie językiem grafów z cyklem; jest to problem kompletny dla NL. Niech HASEDGE będzie językiem grafów z co najmniej jedną krawędzią. Zatem w sposób trywialny nie jest już trudny dla NL, podczas gdy zostaje.CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup...
W książce Arora-Barak w definicji funkcji konstruowalnych w czasie mówi się, że użycie funkcji, które nie są konstruowalne w czasie, może prowadzić do „anomalnych wyników”. Czy ktoś ma przykład takiego „anomalnego wyniku”? Słyszałem w szczególności, że mogą istnieć funkcje, których nie utrzymuje...
Szukam przykładów trudnych problemów (w NP lub trudniejszych) z informatyki, które można sprowadzić do modeli procesów fizycznych. Na przykład max-2-sat można zredukować do minimalizacji energii w modelu Isinga. Chciałbym znaleźć więcej przykładów tego rodzaju
Czy trudno jest apx-przybliżać ułamkową liczbę chromatyczną na wykresach ze stopniem
Macierz Moore'a jest podobna do macierzy Vandermonde, ale ma nieco zmodyfikowaną definicję. http://en.wikipedia.org/wiki/Moore_matrix Jaka jest złożoność obliczenia wyznacznika danego pełnego rzędu macierzy Moore'a modulo jakiejś liczby całkowitej?n × nn×nn \times n Czy wyznacznik Moore'a można...
Niech będzie wykresem niekierowanym. Rozkładem V na podzbiory rozłączne V i nazywa się Hamilton rozkładu z G jeśli subgraph wywołanych przez każdy zestaw V i jest albo wykres Hamiltona lub składa się z jednej krawędzi z | V i | = 2 .G = ( V, E)sol=(V.,mi)G=(V,E)V.V.VV.jaV.jaV_isolsolGV.jaV.jaV_i|...
Czy oznacza ?E = N EE X P = N E X PmiXP.=N.miXP.\mathsf{EXP}=\mathsf{NEXP}E = N
Obliczenia niedeterministycznej maszyny Turinga (NTM) są dobrze znane jako drzewa konfiguracji, zakorzenione w konfiguracji początkowej. Każde przejście w programie jest reprezentowane przez łącze ojciec-dziecko w tym drzewie. Podobne drzewa można również skonstruować do wizualizacji obliczeń...
Wikipedia pisze: FPT zawiera ustalone, możliwe do rozwiązania problemy, które można rozwiązać w czasie dla niektórych funkcji obliczalnych f . Zwykle funkcja ta jest traktowana jako pojedynczy wykładniczy, taki jak 2 O ( k ), ale definicja dopuszcza funkcje, które rosną jeszcze szybciej. Jest to...
Graf decydujący Homomorfizm jest ogólnie NP-Complete. Czy istnieją wyniki, które badają ten problem, gdy leżące u podstaw wykresy mają strukturę algebraiczną (takie jak decydowanie o homomorfizmach z wykresów Coseleya lub Cayleya do innych wykresów o określonej strukturze również)? Oprócz wyników...
Z okazji urodzin Alana Turinga Google opublikował doodle przedstawiające maszynę. Jaką maszyną jest doodle? Czy może wyrażać język Turing Complete? Istnieją oczywiste różnice w stosunku do klasycznej maszyny Turinga: skończona taśma, ograniczenia w sposobie łączenia stanu, ... Doodle jest nadal...
Niech będzie dowolnym EXP kompletnym problemem. Następnie .P A = N P AZAAAP.ZA= NP.ZAPA=NPAP^A = NP^A Niech będzie jakiś wyrocznią, która bierze pod rachunkach zapytań (a TM w P) uczynią, a my możemy dostać .M P B ≠ N P BbBBM.MMP.b≠ N.P.bPB≠NPBP^B \neq NP^B Pytanie: Czy mamy podobne wyniki...
W literaturze nie znalazłem stwierdzenia dotyczącego i ; wskazówki będą mile widziane.N P R PMAMA\mathsf{MA}NPRPNPRP\mathsf{NP}^\mathsf{RP} Wierzę, że są równi: N P R PMA⊆NPRPMA⊆NPRP\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP} : Maszyna zgaduje ciąg Merlina, a wyrocznia weryfikuje ciąg tak,...
W większości probabilistycznych systemów dowodowych (na przykład twierdzenie PCP) prawdopodobieństwa błędów są zwykle definiowane po stronie fałszywie dodatnich, tj. Typowa definicja może wyglądać tak: jeśli to weryfikator zawsze przyjmuje, ale w w innym przypadku prawdopodobieństwo odrzucenia...