Pytania otagowane jako cc.complexity-theory

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

2
Czy znana jest jakaś klasa złożoności zawierająca internetowe odpowiedniki problemów związanych z optymalizacją?
Czy znana jest jakaś klasa złożoności zawierająca internetowe odpowiedniki problemów związanych z optymalizacją? Jeśli nie, to jak można zdefiniować taką klasę? Wiemy, że wiele problemów ma swoją wersję online: np. Wersja online problemu pakowania bin. Problemy online są trudniejsze, ponieważ mierzone są ich współczynnikami konkurencyjności. I nie znalazłem niczego podobnego …
2
NP-kompletne warianty nierozwiązywalnych problemów?
Przykłady ograniczone -Complete wariantów nierozstrzygalnych zestawach:N.P.NPNP Ograniczony problem zatrzymania = { | Maszyna NTM M zatrzymuje się i przyjmuje x w ciągu t kroków}( M, x , 1t)(M,x,1t)(M, x, 1^t)M.MMxxxttt Ograniczone płytki = { | jest płytki kwadratu o powierzchni t 2 za pomocą płytek z T }( T, 1t)(T,1t)(T, …
1
Jakie są złożoności następujących podzbiorów SAT?
Załóżmy, żeP.≠ N.P.P≠NPP \neq NP Do tetracji użyj następującego zapisu (tj. ).jazaia{}^iajaa = aza⋅⋅⋅zaja razyia=aa⋅⋅⋅a⏟i times{}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}} | x | jest wielkością instancji x. Niech L będzie językiem,L |fa( i ) ≤ | x | &lt; g( i ):={x∈L | ∃i∈N, f(i)≤|x|&lt;g(i)}L|f(i)≤|x|&lt;g(i):={x∈L | ∃i∈N, f(i)≤|x|&lt;g(i)}L|_{f(i)\leq |x| < …
3
Czy osadzenie rozwiązania jest możliwe dla SAT?
Interesują mnie „twarde” pojedyncze przypadki problemów z NP. Ryan Williams omówił problem SAT0 na blogu Richarda Liptona . SAT0 pyta, czy instancja SAT ma konkretne rozwiązanie składające się ze wszystkich zer. To skłoniło mnie do myślenia o konstruowaniu instancji SAT, które prawdopodobnie będą „trudne”. Rozważmy wystąpienie SAT z klauzulami i …
1
Twardość problemu z ograniczonym układem gwiezdnym?
Układ gwiazda rodziny n podzbiorów n-elementów przedstawionych . System położony jest graficznym, jeżeli jest jakiś wykres tak, że jest rodzina sąsiedztwie wierzchołków w . To jest kompletne, aby zdecydować, czy dany układ gwiezdny jest graficzny.S G ( V , E ) F G N PFFFSSSG(V,E)G(V,E)G(V,E)FFFGGGNPNPNP Jaka jest minimalna wystąpienie każdego …
5
Klasy złożoności dla przypadków innych niż „najgorszy przypadek”
Czy mamy klasy złożoności w odniesieniu do, powiedzmy, złożoności średnich przypadków? Na przykład, czy istnieje (nazwana) klasa złożoności dla problemów, których podjęcie wymaga wielomianu? Kolejne pytanie dotyczy złożoności najlepszych przypadków , których przykłady przedstawiono poniżej: Czy istnieje klasa (naturalnych) problemów, których decyzja wymaga co najmniej wykładniczego czasu? Aby to wyjaśnić, …
1
Czy badano derandomizację lekko niejednorodnych klas, np. BPP / liniowy?
Przez BPP / linear mam na myśli maszyny BPP z liniową radą, która spełnia obietnicę, gdy otrzyma „prawidłową” radę, a derandomizacja powinna dać nam, powiedzmy, algorytm P / liniowy lub (SUBEXP / liniowy). Jeśli zastosujemy niejednolite założenia, uważam, że klasyczne wyniki powinny zadziałać, ponieważ możemy „oszukać” niejednolitych przeciwników. Jednak przy …
3
Co dowody na to, że
Co dowody na to, że ?c o R P≠ N.P.coRP≠NPcoRP \neq NP jest klasą języków, dla których istnieje probabilistyczna maszyna Turinga, która działa w czasie wielomianowym i zawsze odpowiada Tak na dane wejściowe należące do języka i odpowiada Nie z prawdopodobieństwem co najmniej połowy na dane wejściowe nienależące do języka …
1
Naturalni kandydaci na NP-E i E-NP
Od wczesnych lat 70. wiadomo, że i nie są równe (ponieważ nie jest zamknięty w czasie wielomianowym wiele -jedna redukcja, w przeciwieństwie do ). O ile mi wiadomo, wciąż pozostaje otwarte, czy jedna klasa jest podzbiorem drugiej, czy też są nieporównywalne, co oznacza, że i są niepuste.NPNP{\bf NP}E=DTIME(2O(n))E=DTIME(2O(n)){\bf E}=DTIME(2^{O(n)})EE{\bf E}NPNP{\bf …
1
Jaka jest domniemana zależność między językami P (PTime) i Type 1 (kontekstowymi)?
Nie wiadomo czy P⊆CSLP⊆CSLP\subseteq CSL lub P⊈CSLP⊈CSLP\not\subseteq CSL, gdzie PPP jest zbiorem wszystkich języków rozstrzygalnych w czasie wielomianowym na deterministycznej maszynie Turinga, oraz CSLCSLCSL jest klasą języków kontekstowych, znanych jako równoważne NSPACE(O(n))NSPACE(O(n))NSPACE(O(n)) , języki ustalane przez automaty ograniczane liniowo. W przypadku wielu otwartych pytań istnieje tendencja do jednej odpowiedzi ( …
1
Czy złożoność Kołmogorowa w tabelach prawdy problemu zatrzymania jest znana asymptotycznie?
Pozwolić HALTnHALTnHALT_n oznacz ciąg długości 2n2n2^n odpowiadający tabeli prawdy problemu zatrzymania dla danych wejściowych długości nnn. Jeśli sekwencja złożoności Kołmogorowa K(HALTn)K(HALTn)K(HALT_n) byli O(1)O(1)O(1), wtedy jeden z ciągów porad byłby używany nieskończenie często, a TM z tym ciągiem zakodowanym na stałe byłby w stanie rozwiązać HALTHALTHALT równomiernie nieskończenie często, o czym …
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.