Pytania otagowane jako conditional-results

Dodaj X jako hipotezę, gdzie X nie jest ani prawdziwe, ani fałszywe.

5
Matematyczne implikacje teorii złożoności przypuszcza poza TCS
Czy znasz ciekawe konsekwencje (standardowych) przypuszczeń w teorii złożoności w innych dziedzinach matematyki (tj. Poza informatyką teoretyczną)? Wolałbym odpowiedzi gdzie: hipoteza teorii złożoności jest tak ogólna i standardowa, jak to możliwe; Nie przeszkadzają mi również konsekwencje twardości określonych problemów, ale byłoby miło, gdyby powszechnie uważano, że problemy są trudne (lub …
4
Jakie konkretne dowody istnieją dla P = RP?
RP to klasa problemów rozstrzyganych przez niedeterministyczną maszynę Turinga, która kończy się w czasie wielomianowym, ale dopuszczalny jest również błąd jednostronny. P jest zwykłą klasą problemów rozstrzyganych przez deterministyczną maszynę Turinga, która kończy się w czasie wielomianowym. P = RP wynika z zależności w złożoności obwodu. Impagliazzo i Wigderson wykazali, …
1
Konsekwencje ?
Chociaż twierdzenie Adlemana pokazuje, że , nie znam żadnej literatury badającej możliwe włączenie . Jakie konsekwencje teoretyczne pod względem złożoności miałoby takie włączenie?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP} \subseteq \mathsf{P}/\text{poly} Twierdzenie Adlemana jest czasem nazywane „protoplastą argumentów derandomizacji”. Uważa się, że podlega derandomizacji, podczas gdy nie ma dowodów na to, że „kwantowość” mogłaby …
1
Konsekwencje UP są równe NP
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} (jednoznaczny czas wielomianowy, patrzwikiizoodla odniesienia) jest zdefiniowany jako języki ustalone przez maszynyNPNP\mathsf{NP} …
1
Jakie mamy dowody na ?
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ą ścieżkę akceptacji w instancjach „tak” i brak ścieżki akceptacji w instancjach „nie”.UPUP\mathsf{UP} Oczywiście , …
1
vs
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 parzystości problemy (zobacz to pytanie ), ale być …
2
Konsekwencja PIT w stosunku do bez wydajnego algorytmu
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 pól ogólnych i i istnieje skuteczny algorytm losowy dla tego problemu.Z⊂QZ⊂Q\Bbb Z\subset\Bbb Q Oczekujemy, że ten problem będzie miał skuteczną derandomizację. Jakie …
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.