Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

2
Hierarchie w NP (przy założeniu, że P! = NP)
Zakładając, że P! = NP, uważam, że wykazano, że istnieją problemy, których nie ma w P, a nie w NP-Complete. Przypuszcza się, że takim problemem jest izomorfizm grafów. Czy są jakieś dowody na istnienie większej liczby takich „warstw” w NP? tzn. Hierarchia złożona z więcej niż trzech klas, rozpoczynająca się …
2
Czy istnieje algorytm wielomianowy do określania, czy rozpiętość zbioru macierzy zawiera macierz permutacji?
Chciałbym znaleźć algorytm wielomianowy, który określa, czy rozpiętość danego zestawu macierzy zawiera macierz permutacji. Jeśli ktoś wie, czy ten problem ma inną klasę złożoności, byłoby to równie pomocne. EDYCJA: Oznacziłem to pytanie za pomocą programowania liniowego, ponieważ mam poważne podejrzenia, że ​​gdyby istniało takie rozwiązanie, byłby to rodzaj algorytmu programowania …
3
Uzasadnienie logarytmu f w twierdzeniu o hierarchii DTIME
Jeśli spojrzymy na twierdzenie o hierarchii DTIME, mamy dziennik z powodu narzutu w symulacji deterministycznej maszyny Turinga przez maszynę uniwersalną: DTIME(flogf)⊊DTIME(f)DTIME(flog⁡f)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) Nie mamy tego rodzaju kosztów ogólnych dla NTIME DSPACE. Podstawowe uzasadnienie wynika ze szczegółów dowodu, biorąc pod uwagę różnicę między symulatorami. Moje pytanie jest następujące: bez …
4
Gdyby P = NP były prawdziwe, czy komputery kwantowe byłyby przydatne?
Załóżmy, że P = NP jest prawdziwe. Czy byłoby zatem jakieś praktyczne zastosowanie do budowy komputera kwantowego, takie jak szybsze rozwiązywanie określonych problemów, czy też takie ulepszenie byłoby nieistotne w związku z faktem, że P = NP jest prawdziwe? Jak scharakteryzowałbyś poprawę wydajności, która nastąpiłaby, gdyby komputer kwantowy mógł zostać …
2
Kiedy „X jest kompletne NP” oznacza, że ​​„# X jest kompletne P”?
Niech oznacza problem (decyzji) w NP, a # oznacza jego wersję zliczającą.XXXXXXX Pod jakimi warunkami wiadomo, że „X to NP-zupełny” że „X jest kompletny?⟹⟹\implies Oczywiście istnienie skąpej redukcji jest jednym z takich warunków, ale jest to oczywiste i jedyny taki warunek, o którym wiem. Ostatecznym celem byłoby wykazanie, że żaden …
2
Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym?
Były dwa pytania zadawane niedawno na cs.se które były albo spokrewnione lub miał szczególny przypadek równoznaczne z następującym pytaniem: Załóżmy, że masz ciąg a1,a2,…ana1,a2,…ana_1, a_2, \ldots a_n z nnn liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak aby∑ni=1ai=n(n+1).∑i=1nai=n(n+1).\sum_{i=1}^n a_i = n(n+1).ππ\piσσ\sigma1…n1…n1 \dots nai=πi+σiai=πi+σia_i = …
2
Derandomizacja Valiant-Vazirani?
Twierdzenie Valiant-Vazirani mówi, że jeśli istnieje wielomianowy algorytm czasu (deterministyczny lub losowy) do rozróżniania między formułą SAT, która ma dokładnie jedno zadowalające przypisanie, a formułą niezadowalającą - wówczas NP = RP . Twierdzenie to zostało udowodnione poprzez wykazanie, że UNIQUE-SAT jest NP- twardy przy randomizowanych redukcjach. Z zastrzeżeniem prawdopodobnych przypuszczeń …
3
Czy NPI jest zawarty w P / poly?
Przypuszcza się, że ponieważ odwrotność oznaczałaby . Twierdzenie Ladnera stwierdza, że ​​jeśli a następnie . Wydaje się jednak, że dowód nie uogólnia na więc możliwość ie wydaje się otwarty.NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}PH=Σ2PH=Σ2\mathsf{PH} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne \mathsf{NP}NPI:=NP∖(NPC∪P)≠∅NPI:=NP∖(NPC∪P)≠∅\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptysetP/polyP/poly\mathsf{P}/\text{poly}NPI⊂P/polyNPI⊂P/poly\mathsf{NPI} \subset \mathsf{P}/\text{poly}NP⊂NPC∪P/polyNP⊂NPC∪P/poly\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly} Zakładając, że …
2
Hierarchia dla BPP a derandomizacja
W jednym zdaniu: czy istnienie hierarchii dla oznaczałoby jakiekolwiek wyniki derandomizacji?BPTIMEbP.T.jaM.mi\mathsf{BPTIME} Powiązane, ale niejasne pytanie brzmi: czy istnienie hierarchii dla implikuje jakieś trudne dolne granice? Czy rozwiązanie tego problemu uderza w znaną barierę w teorii złożoności?BPTIMEbP.T.jaM.mi\mathsf{BPTIME} Moim motywem do tego pytania jest zrozumienie względnej trudności (w odniesieniu do innych głównych …
1
Współczynniki Fouriera Funkcje boolowskie opisane przez obwody o ograniczonej głębokości z bramkami AND OR i XOR
Niech faff będzie funkcją boolowską i pomyślmy o f jako funkcji od {−1,1}n{−1,1}n\{-1,1\}^n do {−1,1}{−1,1}\{ -1,1 \} . W tym języku ekspansja Fouriera f jest po prostu ekspansją f pod względem kwadratowych wolnych jednomianów. (Te 2n2n2^n monomialów stanowią podstawę dla przestrzeni funkcji rzeczywistych na {−1,1}n{−1,1}n\{-1,1\}^n . Suma kwadratów współczynników wynosi …
3
Certyfikat CoNP dla Graph Isomorphism
Łatwo zauważyć, że izomorfizm wykresu (GI) występuje w NP. Poważnym otwartym problemem jest to, czy GI jest w CoNP. Czy są potencjalni kandydaci właściwości grafów, które można wykorzystać jako certyfikaty CoNP dla GI? Jakieś przypuszczenia, które sugerują, że ? Jakie są implikacje ?GI∈coNPGI∈coNPGI \in coNPGI∈coNPGI∈coNPGI \in coNP
2
Metoda wielomianowa dla wyników złożoności
Metody wielomianowe , powiedzmy twierdzenie kombinatoryczne Nullstellensatz i twierdzenie Chevalleya-Ostrzegania, są potężnymi narzędziami w kombinatywnej addytywności. Reprezentując problem z właściwymi wielomianami, mogą zagwarantować istnienie rozwiązania lub liczbę rozwiązań wielomianów. Zostały one wykorzystane do rozwiązania problemów, takich jak ograniczone zestawy sum lub problemy o sumie zerowej , a niektóre twierdzenia w …
7
Udowadnianie dolnych granic przez udowodnienie górnych granic
Niedawny wynik Ryana Williamsa w przełomowym złożoności obwodu w dolnej granicy zapewnia technikę dowodową, która wykorzystuje wynik górnej granicy w celu udowodnienia niższych granic złożoności. Suresh Venkat w swojej odpowiedzi na to pytanie: Czy są jakieś sprzeczne z intuicją wyniki w informatyce teoretycznej? , podał dwa przykłady ustanawiania dolnych granic …
1
Funkcje, które nie są wydajnie obliczalne, ale można się ich nauczyć
Wiemy, że (patrz np. Twierdzenia 1 i 3 z [1]), z grubsza mówiąc, w odpowiednich warunkach, funkcje, które mogą być skutecznie obliczone przez maszynę Turinga w czasie wielomianowym („wydajnie obliczalne”), mogą być wyrażone przez wielomianowe sieci neuronowe z rozsądnymi rozmiarami, a zatem można się go nauczyć z wielomianową złożonością próbki …
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.