Pytania otagowane jako complexity-classes

Klasy złożoności obliczeniowej i ich relacje

2
Problemy, które można rozstrzygać, ale których nie można zweryfikować w czasie wielomianowym
Pracując nad nieco niezwiązanym projektem dla Suresh, ostatnio natknąłem się na pracę wykonaną przez Page i Opper na temat systemów tworzonych przez użytkowników, a część ich pracy krótko omówiła problemy, których nie można zweryfikować w czasie wielomianowym. Nie udało mi się znaleźć wielu informacji o innych problemach, których nie można …
2
Czy
Przez http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Jeśli jest językiem PSPACE uzupełniania, P = N P A .AAAPA=NPAPA=NPAP^{A}=NP^{A} Jeśli jest deterministyczną wyrocznią wielomianową, P B ≠ N P B (przy założeniu P ≠ N P ).BBBPB≠NPBPB≠NPBP^{B}\ne NP^{B}P≠NPP≠NPP\ne NP to klasa problemów decyzyjnych analogiczna dla # P i P ⊆ P P ⊆ P S P …
3
Czy istnieje naturalne ograniczenie logiki VO, która przechwytuje P lub NP?
Papier Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre zapytania, które nie są obliczalne. (Jak wskazał Arthur …
2
Minimalna szerokość drzewa obwodu dla WIĘKSZOŚCI
Jaka jest minimalna szerokość drzewa obwodu powyżej {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} do obliczenia MAJ? Tutaj MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} wyprowadza 1, jeśli co najmniej połowa jego danych wejściowych to 111 . Dbam tylko o rozmiar obwodu (powinien być wielomianowy) i że dane wejściowe powinny być odczytywane tylko raz, chociaż rozwarcie bramki wejściowej może …
2
Zmniejszenie P vs. NP do SAT
W poniższym pytaniu wykorzystano pomysły z kryptografii zastosowane w teorii złożoności. To powiedziawszy, jest to pytanie teoretycznie złożone, i aby odpowiedzieć na to pytanie, nie jest wymagana żadna wiedza kryptograficzna. Celowo piszę to pytanie bardzo nieformalnie. Brakuje szczegółów, prawdopodobnie jest to nieco niepoprawnie podane. Prosimy o wskazanie poprawek w swoich …
1
Konsekwencje
Mam część próbnej próby ⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}. Próba dowodowa polega na zmniejszeniu karpu z⊕P⊕P\oplus \mathbf{P}-kompletny problem ⊕⊕\oplus3-REGULARNA POKRYWA VERTEX do SAT. Biorąc pod uwagę sześcienny wykres GGG, redukcja generuje wzór CNF FFF posiadający obie następujące właściwości: FFF ma co najwyżej 111 spełniające zadanie. FFF jest zadowalający tylko i tylko …
1
Czy DSPACE (n) = DSPACE (1,5n)?
Z twierdzenia o hierarchii przestrzeni wiadomo, że jeśli faff można konstruować w przestrzeni, to DSPACE ( 2 f( n )2f(n)2f(n) ) nie jest równe DSPACE ( fa( n ) )f(n))f(n)) . Tutaj przez DSPACE ( fa( n ) )f(n))f(n)) mam na myśli klasę wszystkich problemów, które można rozwiązać w przestrzeni …
1
vs
Czy ? Lub, bardziej ogólnie, czy ?NPPP=PPPNPPP=PPP\mathsf{NP^{PP}} = \mathsf{P^{PP}}NPPP⊆PPP/polyNPPP⊆PPP/poly\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}
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.