Pytania otagowane jako polynomial-time

Treewith jest ważnym parametrem grafu, który wskazuje, jak blisko wykres jest od drzewa (choć nie w ścisłym sensie topologicznym). Powszechnie wiadomo, że obliczenie szerokości jest trudne dla NP. Czy są jakieś naturalne klasy wykresów, w których trudno jest obliczyć szerokość ? Podobnie: Czy istnieją ciekawe klasy grafów, w których obliczanie …

13 graph-theory  np-hardness  polynomial-time  treewidth 

P / poly to klasa problemów decyzyjnych rozwiązanych przez rodzinę obwodów boolowskich wielkości wielomianowych. Alternatywnie można go zdefiniować jako wielomianową maszynę Turinga, która otrzymuje ciąg porady, który jest wielomianem wielkości w n, i który opiera się wyłącznie na rozmiarze n. mP / poli to klasa problemów decyzyjnych rozwiązanych przez rodzinę …

13 cc.complexity-theory  complexity-classes  circuit-complexity  polynomial-time  monotone 

Czy znasz jakieś problemy (najlepiej przynajmniej nieco dobrze znane), w których dla praktycznego rozmiaru problemu algorytm wykładniczy działa znacznie szybciej niż najbardziej znany odpowiednik czasu wielomianowego. Załóżmy na przykład, że problem ma praktyczny rozmiar * i istnieją dwa znane algorytmy: jeden to a drugi to dla pewnej stałej . Oczywiście …

13 time-complexity  polynomial-time  exp-time-algorithms 

Próbując rozwiązać problem, ostatecznie wyraziłem jego część jako następujący program liczbowy całkowity. Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całki:ℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,wℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,w\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},wxijxijx_{ij} Zminimalizować ∑mj=1cj∑ℓi=1xij∑j=1mcj∑i=1ℓxij\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij} Z zastrzeżeniem: ∑mj=1xij=ni∀i∑j=1mxij=ni∀i\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i ∑ℓi=1xij≥w∀j∑i=1ℓxij≥w∀j\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j Chciałbym wiedzieć, czy ten program …

13 reference-request  linear-programming  polynomial-time  integer-programming  integrality-gap 

Rozważ następujący problem, Biorąc pod uwagę zestaw dodatnimi liczbami { 1 , ... , n } , w którym K ≥ 3 jest stała, chcemy podzielić wkomponowany m podzbiorów wielkości K , przy czym produkt z sumy każdego podzbioru jest zmaksymalizowane.n=kmn=kmn = k m{a1,…,an}{a1,…,an}\{ a_1, \dots, a_n \}k≥3k≥3k \ge 3mmmkkk …

12 cc.complexity-theory  np-hardness  application-of-theory  polynomial-time 

Rozważ dołączony niekierowany wykres z nieujemnymi wagami krawędzi i dwoma wyróżnionymi wierzchołkami . Poniżej przedstawiono niektóre problemy ze ścieżką, które mają następującą postać: znajdź ścieżkę , tak aby jakaś funkcja ciężaru krawędzi na ścieżce była minimalna. W tym sensie wszyscy są „krewnymi” problemu najkrótszej ścieżki; w tym ostatnim funkcja jest …

10 graph-theory  graph-algorithms  np-complete  polynomial-time 

W zoo o złożoności napisano [ 1 ], że w złożoności opisowej można zdefiniować za pomocą trzech różnych rodzajów wzorów, który jest również , a także jako .PPPFO(LFP)FO(LFP)FO(LFP)FO(nO(1))FO(nO(1))FO(n^{O(1)})SO(HORN)SO(HORN)SO(HORN) Istnieją jednak pewne wyjątki, na przykład nie może być wyrażona przez FP (FP ma taką samą moc ekspresji z LFP). i nie …

10 lo.logic  polynomial-time  descriptive-complexity 

Twierdzenie Mahaneya mówi nam, że jeśli istnieje rzadki zestaw przy wielomianowych redukcjach wielokrotności jeden, to . (Patrz „ Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa ”)NPNPNPP=NPP=NPP = NP Czy znane są konsekwencje istnienia rzadkich kompletnych zestawów dla innych klas złożoności? W szczególności, jeśli w obszarze logarytmicznym występuje …

10 cc.complexity-theory  complexity-classes  reductions  polynomial-time  logspace 

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 ( …

10 cc.complexity-theory  fl.formal-languages  polynomial-time 

Przepraszam, to trochę „miękkie” pytanie. Teoria informacji nie ma pojęcia złożoności obliczeniowej. Na przykład instancja SAT lub instancja SAT plus bit wskazujący na satysfakcję niosą tę samą ilość informacji. Czy istnieje sposób sformalizowania pojęcia „wielomianowo poznawalny”? Takie ramy mogą definiować na przykład pojęcie dywergencji wielomianowej KL między zmienną losową X …

9 cc.complexity-theory  it.information-theory  polynomial-time