EDYCJA na 2011/02/08: Po znalezieniu i przeczytaniu niektórych odniesień postanowiłem rozdzielić oryginalne pytanie na dwa osobne. Oto część dotycząca UP vs NP, w części dotyczącej klas syntaktycznych i semantycznych zobacz Korzyści dla klas syntaktycznych i semantycznych . UPUP\mathsf{UP}...
Ostatnio Watrous i wsp. Udowodnili, że QIP (3) = PSPACE to niezwykły wynik. Był to dla mnie zaskakujący wynik, co wywołało u mnie myśl ... Zastanawiałem się, czy komputery kwantowe mogłyby być skutecznie symulowane przez komputery klasyczne. Czy może to być PO PROSTU związane z podziałem między IP...
Zgodnie z sugestią Josha Grochowa przekształcam swój komentarz z poprzedniego pytania w nowe pytanie. Jakie mamy dowody na ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Tutaj to klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga o wielomianowym czasie, które mają unikalną...
W naszej ostatniej pracy rozwiązujemy problem obliczeniowy, który powstał w kontekście kombinatorycznym, przy założeniu, że , gdzie to -wersja . Jedyny artykuł na temat , który znaleźliśmy, to artykuł Beigel-Buhrman-Fortnow 1998 , cytowany w Zoo Complexity . Rozumiemy, że możemy wziąć wersje...
Ostatnie pytanie (patrz Konsekwencje NP = PSPACE ) dotyczyło „paskudnych” konsekwencji . W odpowiedziach wymieniono kilka skutków zawalenia, w tym i inne, dostarczając wielu powodów, aby wierzyć .N P = c o N P N P ≠ P S P A C EN.P.= PS.P.A C.miNP=PSPACENP=PSPACEN.P.= c o NP.NP=coNPNP=coNPN.P.≠...
Wiemy, że jeśli wówczas całe PH załamuje się. Co się stanie, jeśli hierarchia wielomianowa ulegnie częściowemu zawaleniu? (Lub jak zrozumieć, że PH może spaść powyżej pewnego punktu, a nie poniżej?)P=NPP=NPP=NP Krótko mówiąc, jakie byłyby konsekwencje i P ≠ N P ?NP=coNPNP=coNPNP=coNPP≠NPP≠NPP\ne...
jest powszechnie przypuszczane, że jest fałszywe.R P= NP.RP.=N.P.RP = NP Ale wyobraź sobie przez chwilę, że to prawda. W takim przypadku, jakie jest prawdopodobieństwo, że ?P.= NP.P.=N.P.P = NP Innymi słowy: w świecie, w którym , co może być nadal postrzegane jako przeszkoda dla nas, aby wierzyć...
oznacza N P ⊆ P / P O l y , który z kolei ma wpływ interesujące jak załamania wielomianu hierarchii.P/poly=NP/polyP/poly=NP/polyP/poly = NP/polyNP⊆P/polyNP⊆P/polyNP \subseteq P/poly Czy są interesujące implikacje dla ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq
w 1979 r. Hopcroft / Ullman napisał, że L ⊆ P ⊆ NP ⊆ PSpace jest znany, ale L ⊊ PSpace jest jedynym właściwym (i trywialnym) zabezpieczeniem znanym, chociaż wszystkie są przypuszczane, że są odpowiednimi zabezpieczeniami i „tam, gdzie rzeczy nadal istnieją” ~ 4 dekady później . od tego czasu...
Biorąc pod uwagę tak, że współczynniki są ograniczone przez , czy trzymać?p , q B p ≡ qp(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Obowiązuje tutaj lemat Schwartza-Zippela, ponieważ dotyczy on...
Czy oznacza ?E = N EE X P = N E X PmiXP.=N.miXP.\mathsf{EXP}=\mathsf{NEXP}E = N