Czy jest jakiś realizowany projekt formalnej weryfikacji twierdzeń i dowodów teorii złożoności przy użyciu asystenta dowodu, takiego jak Coq? Czy są jakieś granice?
Czy istnieje , język NP lub P-zupełny, który ma pewną rodzinę grup symetrii G n (lub groupoid , ale wtedy pytania algorytmiczne stają się bardziej otwarte) działając (w czasie wielomianowym) na zbiorach L n = { l ∈ L ∣ | l | = n } tak, że jest kilka …
W grze żwirowej na linii znajdują się N + 1 węzłów oznaczonych od 0 do N. Gra rozpoczyna się od kamyka w węźle 0. Jeśli kamyk znajduje się w węźle i, możesz dodać lub usunąć kamyk z węzła i + 1. Celem jest umieszczenie kamyka na węźle N, bez umieszczania …
Wiadomo, że w przypadku następnie wielomian hierarchia zapada się Ď P 2 i M A = A M .N.P.⊆ P./ PO l rNP⊆P/PolyNP\subseteq P/PolyΣP.2)Σ2P\Sigma_2^{P}M.= MMA=AMMA = AM Jakie są najsilniejsze znane upadki, jeśli ?N.miXP.⊆ P./ PO l rNEXP⊆P/PolyNEXP\subseteq P/Poly
W swojej książce Computational Complexity Papadimitriou definiuje FNP w następujący sposób: Załóżmy, że jest językiem w NP . Propozycja według 9.1 jest rozstrzygalne wielomianowego razem wielomianowo zrównoważony stosunek R L takie, że dla wszystkich ciągów x : jest łańcuch Y z R L ( x , y ) , wtedy …
W pracy Stephena Cooka na temat problemu P vs NP [1] stwierdza, że [2]: Teza wykonalności: Naturalny problem ma wykonalny algorytm, jeśli ma algorytm czasu wielomianowego. Moje pytanie brzmi: co dokładnie on (lub ogólnie tak naprawdę, co to znaczy) przez „ naturalny problem”? Mówienie o naturalnych problemach wydaje się dość …
Czy fakt, że problem jest zakończony w czasie EXP, sugeruje, że A nie występuje w D T I M E ( 2 o ( n ) ) ?AAAAAADTIME(2o(n))DTIME(2o(n))DTIME(2^{o(n)}) Wiem, że według twierdzenia o hierarchii czasu nie jest uwzględnione w E = D T I M E ( 2 O ( …
KRÓTKIE PYTANIE: Czy MAJ-3CNF jest problemem kompletnym z PP przy wielu redukcjach? DŁUŻSZA WERSJA: Dobrze wiadomo, że MAJSAT (decydujący, czy większość przypisań zdania zdaniowego spełnia zdanie) jest PP-kompletny przy wielu redukcjach jeden, a #SAT jest # P-kompletny przy redukcjach oszczędnych. Oczywiste jest również, że # 3CNF (czyli #SAT ograniczony do …
Biorąc pod uwagę silne generatory dla grupy działającej na ciągach bitów o długości i elemencie , jak trudno jest obliczyć leksykograficznie minimalny element , orbity w ?( G ≤S.n, ∗ )(sol≤S.n,∗)(G \leq S_n, *)nnns ∈ { 0 , 1}ns∈{0,1}ns \in \{0, 1\}^nG . ssol.sG.sssssolsolG
Mamy problem i znaleźliśmy algorytm, który wydaje się być 2-sekundowy. Chciałbym znaleźć znane problemy z niepełnym czasem 2, aby znaleźć dolną granicę. W literaturze znalazłem głównie dwa takie problemy: czy PCP jako rozwiązanie o rozmiarze mniejszym niż 2)2)n2)2)n2^{2^n} i problem uprawy roli dla kwadratu wielkości 2)2)n2)2)n2^{2^n} Jednak nie byłem w …
Nie wiadomo, czy NEXP jest zawarty w P / poli. Rzeczywiście udowodnienie, że NEXP nie jest w P / poli, miałoby pewne zastosowania w derandomizacji. Jaka jest najmniejsza jednolita klasa C, dla której można udowodnić, że C nie jest zawarte w P / poli? Czy wykazanie, że ko-NEXP nie jest …
Używamy plików cookie i innych technologii śledzenia w celu poprawy komfortu przeglądania naszej witryny, aby wyświetlać spersonalizowane treści i ukierunkowane reklamy, analizować ruch w naszej witrynie, i zrozumieć, skąd pochodzą nasi goście.
Kontynuując, wyrażasz zgodę na korzystanie z plików cookie i innych technologii śledzenia oraz potwierdzasz, że masz co najmniej 16 lat lub zgodę rodzica lub opiekuna.