Pytania otagowane jako complexity-theory

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

1
Najszybsza znana złożoność kombinatorycznego algorytmu ILP?
Zastanawiam się, co jest najbardziej znany algorytm, jeśli chodzi o Big- notacji, aby rozwiązać Programowanie Integer Linear?OOO Wiem, że problem jest , więc nie oczekuję niczego wielomianowego. Wiem, że istnieje wiele heurystyk, które są wykorzystywane w praktycznych zastosowaniach, takich jak CPLEX, ale bardziej interesuje mnie formalna, w najgorszym przypadku złożoność …
1
Dowód twierdzenia Karpa-Liptona
Próbuję zrozumieć dowód twierdzenia Karp-Lipton, jak stwierdzono w książce „Złożoność obliczeniowa: nowoczesne podejście” (2009). W szczególności ta książka stwierdza, co następuje: Twierdzenie Karpa-Liptona Jeśli NP , to PH .P ∖ p o l y⊆⊆\subseteq P∖polyP∖polyP_{\backslash poly} =Σp2=Σ2p= \Sigma^p_2 Dowód: Zgodnie z twierdzeniem 5,4, w celu wykazania pH , to wystarczy, …
2
Czy istnieje skuteczny algorytm równoważności wyrażeń?
np. xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) ? Wyrażenia pochodzą ze zwykłej algebry w szkole średniej, ale ograniczają się do dodawania i mnożenia arytmetycznego (np. 2+2=4;2.3=62+2=4;2.3=62+2=4; 2.3=6 ), bez odwrotności, odejmowania lub dzielenia. Litery są zmiennymi. Jeśli to pomoże, możemy zabronić jakiegokolwiek wyrażenia reprezentowanego przez wartości liczbowe inne niż 111 ; tzn. nie x2x2x^2 ani …
2
Czy istnieją ustalone klasy złożoności z liczbami rzeczywistymi?
Niedawno student poprosił mnie o sprawdzenie dla nich dowodu twardości NP. Dokonali redukcji zgodnie z: Zmniejszam ten problem P′P′P' którym wiadomo, że jest NP-kompletny do mojego problemu PPP (z redukcją wielokrotnego wielokrotności jeden), więc PPP jest NP-twardy. Moja odpowiedź brzmiała w zasadzie: Ponieważ PPP ma instancje z wartościami z RR\mathbb{R} …
6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if …
3
Złożoność problemu adopcji kociąt
To pojawiło się, gdy próbowałem odpowiedzieć na to pytanie dotyczące minimalizacji długości przewodów . Miałem to nazwać problemem „poligamicznego małżeństwa”, ale internet, tak kocięta. Tak! Załóżmy, że mamy kociąt, które muszą być przyjęte przez ludzi, . Dla każdego kociaka, i każdej osoby kosztuje . Chcielibyśmy zminimalizować całkowity koszt przyjęcia wszystkich …
2
Kilka pytań na temat obliczeń równoległych i klasy NC
Mam wiele powiązanych pytań dotyczących tych dwóch tematów. Po pierwsze, większość tekstów złożoności tylko tuszować klasę . Czy istnieje dobry zasób, który bardziej szczegółowo omawia badania? Na przykład coś, co omawia wszystkie moje pytania poniżej. Ponadto, jestem przy założeniu, że N C nadal widzi ilość godziwą badań ze względu na …
2
Kompromis czasowo-przestrzenny dla problemu brakującego elementu
Oto dobrze znany problem. Biorąc pod uwagę tablicę A[1…n]A[1…n]A[1\dots n] dodatnich liczb całkowitych, wyprowadzaj najmniejszą dodatnią liczbę całkowitą spoza tablicy. Problem można rozwiązać w przestrzeni i czasie O(n)O(n)O(n) : przeczytaj tablicę, śledź w przestrzeni O(n)O(n)O(n) czy wystąpiło 1,2,…,n+11,2,…,n+11,2,\dots,n+1 poszukaj najmniejszego elementu. Zauważyłem, że możesz wymieniać przestrzeń na czas. Jeśli masz …
2
Czy każdy problem NP ma wielocząsteczkowy preparat ILP?
Ponieważ całkowite programowanie liniowe jest zakończone NP, występuje zmniejszenie Karp z dowolnego problemu w NP. Pomyślałem, że to sugeruje, że zawsze istnieje wielomianowa formuła ILP dla dowolnego problemu w NP. Ale widziałem artykuły na temat konkretnych problemów związanych z NP, w których ludzie piszą takie rzeczy, jak: „to jest pierwszy …
1
Bezpośrednia redukcja z
Wiemy, że jest w według twierdzenia Immermana – Szelepcsényiego, a ponieważ jest dlatego to wiele-jeden obszar dziennika, który można zredukować do . Ale czy istnieje bezpośrednia / kombinatoryczna redukcja, która nie przechodzi przez wykres konfiguracji maszyn Turinga w ?st-non-connectivityst-non-connectivityst\text{-}non\text{-}connectivityNLNL\mathsf{NL}st-connectivityst-connectivityst\text{-}connectivityNL-hardNL-hard\mathsf{NL\text{-}hard}st-non-connectivityst-non-connectivityst\text{-}non\text{-}connectivityst-connectivityst-connectivityst\text{-}connectivityNLNL\mathsf{NL} stConnectivitystConnectivity\mathsf{stConnectivity} (a.k.a. stPATHstPATHstPATH): Given directed graph GGG and vertices sss and …
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.