Pytania otagowane jako np-complete

Pytania dotyczące najtrudniejszych problemów w NP, tj. Tych, które można rozwiązać w czasie wielomianowym za pomocą niedeterministycznych maszyn Turinga.

1
Wnioskowanie o rodzajach uściślenia
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if …
11 programming-languages  logic  type-theory  type-inference  machine-learning  data-mining  clustering  order-theory  reference-request  information-theory  entropy  algorithms  algorithm-analysis  space-complexity  lower-bounds  formal-languages  computability  formal-grammars  context-free  parsing  complexity-theory  time-complexity  terminology  turing-machines  nondeterminism  programming-languages  semantics  operational-semantics  complexity-theory  time-complexity  complexity-theory  reference-request  turing-machines  machine-models  simulation  graphs  probability-theory  data-structures  terminology  distributed-systems  hash-tables  history  terminology  programming-languages  meta-programming  terminology  formal-grammars  compilers  algorithms  search-algorithms  formal-languages  regular-languages  complexity-theory  satisfiability  sat-solvers  factoring  algorithms  randomized-algorithms  streaming-algorithm  in-place  algorithms  numerical-analysis  regular-languages  automata  finite-automata  regular-expressions  algorithms  data-structures  efficiency  coding-theory  algorithms  graph-theory  reference-request  education  books  formal-languages  context-free  proof-techniques  algorithms  graph-theory  greedy-algorithms  matroids  complexity-theory  graph-theory  np-complete  intuition  complexity-theory  np-complete  traveling-salesman  algorithms  graphs  probabilistic-algorithms  weighted-graphs  data-structures  time-complexity  priority-queues  computability  turing-machines  automata  pushdown-automata  algorithms  graphs  binary-trees  algorithms  algorithm-analysis  spanning-trees  terminology  asymptotics  landau-notation  algorithms  graph-theory  network-flow  terminology  computability  undecidability  rice-theorem  algorithms  data-structures  computational-geometry 
1
Czy wszystkie znane algorytmy rozwiązywania problemów NP-zupełnych są konstruktywne?
Czy są znane algorytmy, które poprawnie wypisują odpowiedź „tak” dla problemu NP-complete bez pośredniego generowania certyfikatu? Rozumiem, że łatwo jest przekształcić wyrocznię spełniającą w znajdującą satysfakcjonujące zadanie: po prostu iteruj po zmiennych, za każdym razem pytając wyrocznię spełniającą o rozwiązanie związku tej zmiennej z pierwotnym problemem. Ale czy takie opakowanie …
2
Czy ta klasyczna gra z układankami NP-zupełna?
Istnieje klasyczna gra logiczna, bardzo podobna do krzyżówki, z tą różnicą, że podana jest lista słów, a następnie podana jest kwadratowa tablica złożona z kwadratów jednostkowych, z niektórymi kwadratami zaciemnionymi jak krzyżówka, a na niektórych kwadratach jest już napisany list. Celem jest zapisanie każdego słowa z listy raz i tylko …
2
Czy możemy skonstruować redukcję Karp z redukcji Cooka między problemami NP?
Mieliśmy kilka pytań na temat relacji redukcji Cooka i Karp . Oczywiste jest, że redukcje Cooka (redukcje Turinga w czasie wielomianowym) nie definiują tego samego pojęcia kompletności NP jak redukcje Karp (redukcje w postaci wielomianu w jednym czasie), które są zwykle stosowane. W szczególności redukcje Cooka nie mogą oddzielić NP …
3
Przypisanie numeru
Biorąc pod uwagę liczb tak, że istnieje przypisanie liczb który jest permutacją taki, żeA 1 ≤ A 2 ≤ . . . ≤ A k k ∑kkkA1≤A2≤...≤AkA1≤A2≤...≤AkA_1 \leq A_2 \leq ... \leq A_k∑i=1kAi=k(2k+1)∑i=1kAi=k(2k+1)\sum\limits_{i=1}^k A_i = k(2k + 1)i1,i2,...,i2ki1,i2,...,i2ki_1, i_2, ... , i_{2k}1,2,...,2k1,2,...,2k1, 2, ... , 2k i1+i2≤A1i3+i4≤A2...i2k−1+i2k≤Aki1+i2≤A1i3+i4≤A2...i2k−1+i2k≤Aki_1 + i_2 \leq …
1
Problem z kamykami
Pebbling to gra w pasjansa rozgrywana na niekierowanym grafie , gdzie każdy wierzchołek ma zero lub więcej kamyków. Pojedynczy ruch kamyka polega na usunięciu dwóch kamyków z wierzchołka v i dodaniu jednego kamyka do dowolnego sąsiada v . (Oczywiście, wierzchołek v musi mieć co najmniej dwa kamyki przed ruchem). Problem …
1
Intuicja stojąca za relatywizacją
Biorę kurs na złożoność obliczeniową. Mój problem polega na tym, że nie rozumiem metody relatywizacji . Próbowałem znaleźć odrobinę intuicji w wielu podręcznikach, jak dotąd niestety bez powodzenia. Będę wdzięczny, jeśli ktoś może rzucić światło na ten temat, abym mógł kontynuować sam. Kilka kolejnych zdań to pytania, a moje przemyślenia …
2
NP-Kompletność problemu kolorowania wykresu
Alternatywne sformułowanie Wymyśliłem alternatywne sformułowanie do poniższego problemu. Alternatywne sformułowanie jest w rzeczywistości szczególnym przypadkiem poniżej problemu i wykorzystuje dwuczęściowe wykresy do opisania problemu. Uważam jednak, że alternatywny preparat jest nadal trudny do NP. Alternatywne sformułowanie wykorzystuje rozłączny zestaw przychodzących i wychodzących węzłów, co upraszcza definicję problemu. Biorąc pod uwagę …
3
Czy łączenie wysp z pontonami NP-zupełne?
Mam w głowie problem, myślę, że jest to problem NPC, ale nie wiem, jak to udowodnić. Oto problem: Istnieje k wyspy w bardzo dużym jeziorem, a tam są n kształcie wachlarza pontony. Te pontony są tego samego rozmiaru, ale mają różne początkowe kierunki i znajdują się w różnych oryginalnych pozycjach …
1
Twardość i kierunki redukcji
Powiedzmy, że wiemy, że problem A jest trudny, a następnie redukujemy A do nieznanego problemu B, aby udowodnić, że B jest również trudny. Jako przykład: wiemy, że 3-kolorowanie jest trudne. Następnie redukujemy kolorowanie 3 do koloru 4. Po połączeniu jednego z kolorów 3-kolorowania masz 4-kolory, ergo 4-kolory są trudne. Właśnie …
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.