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.

7
Czy ustawodawstwo NP jest kompletne?
Chciałbym wiedzieć, czy były prace związane z kodeksem prawnym złożoności. W szczególności, przypuśćmy, że mamy problem decyzyjny „Czy biorąc pod uwagę tę książkę prawniczą i ten szczególny zestaw okoliczności, pozwany jest winny?” Do jakiej klasy złożoności należy? Są wyniki, które dowiodły, że gra karciana Magic: the Gathering jest zarówno NP, …
6
Dlaczego niektóre gry są kompletne?
Przeczytałem wpis w Wikipedii na temat „ Listy problemów z NP-complete ” i odkryłem, że gry takie jak Super Mario, Pokemon, Tetris lub Saga Crush Candy są na przykład kompletne. Jak mogę sobie wyobrazić np. Kompletność gry? Odpowiedzi nie muszą być zbyt precyzyjne. Chcę tylko uzyskać przegląd tego, co oznacza, …
3
Problem z plecakiem - NP-kompletny pomimo dynamicznego rozwiązania programistycznego?
Problemy z plecakiem można łatwo rozwiązać za pomocą programowania dynamicznego. Programowanie dynamiczne przebiega w czasie wielomianowym; dlatego to robimy, prawda? Przeczytałem, że jest to w rzeczywistości problem NP-zupełny, co oznaczałoby, że rozwiązanie problemu wielomianowego jest prawdopodobnie niemożliwe. Gdzie jest mój błąd?
4
Jak mogę zweryfikować rozwiązanie problemu Traveling Salesman w czasie wielomianowym?
Tak więc problem decyzyjny TSP (problem sprzedawcy podróży) jest NP kompletny . Ale nie rozumiem, w jaki sposób mogę sprawdzić, czy dane rozwiązanie TSP jest w rzeczywistości optymalne w czasie wielomianowym, biorąc pod uwagę, że nie ma sposobu na znalezienie optymalnego rozwiązania w czasie wielomianowym (co jest spowodowane tym, że …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
6
Generowanie kombinacji z zestawu par bez powtarzania elementów
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …
3
Problemy z NP-zupełnością nie „oczywiście” w NP
Wielu przyszło na myśl, że we wszystkich dowodach kompletności , które przeczytałem (które pamiętam), zawsze trywialne jest pokazanie, że problem jest w i pokazanie, że jest to -hard jest ... trudną częścią. Jakie problemy zakończone to te, których weryfikatory czasu wielomianowego są wysoce nietrywialne?NP NP NPNPNP\textbf{NP}NPNP\textbf{NP}NPNP\textbf{NP}NPNP\textbf{NP}
1
Czy regex golf NP-Complete?
Jak widać na ostatnim pasku XKCD i najnowszym poście na bloguwedług Petera Norviga (i opowiadania Slashdota z tym ostatnim) „regex golf” (który można by lepiej nazwać problemem separacji wyrażeń regularnych) jest zagadką polegającą na zdefiniowaniu najkrótszego możliwego wyrażenia regularnego, które akceptuje każde słowo w zestawie A i nie ma słowa …
2
Ogólna zasada, aby wiedzieć, czy problem może być NP-zupełny
To pytanie zostało zainspirowane komentarzem na StackOverflow . Oprócz znajomości problemów NP-zupełnych z książki Garey Johnson i wielu innych; czy istnieje ogólna zasada, aby wiedzieć, czy problem wygląda jak NP-zupełny? Nie szukam czegoś rygorystycznego, ale czegoś, co działa w większości przypadków. Oczywiście za każdym razem, gdy musimy udowodnić, że problem …
1
Najdłuższa powtarzająca się (rozproszona) sekwencja w ciągu
Nieformalne oświadczenie o problemie: Biorąc pod uwagę ciąg znaków, np. ACCABBABACCABBABACCABBAB , chcemy pokolorować niektóre litery na czerwono, a niektóre na niebiesko (a niektóre wcale), tak że czytanie tylko czerwonych liter od lewej do prawej daje taki sam wynik jak czytanie tylko niebieskie litery. W przykładzie możemy je pokolorować w …
3
Nauczanie kompletności NP - redukcje Turinga i karp
Interesuje mnie pytanie, jak najlepiej uczyć kompletności NP na kierunkach informatycznych. W szczególności, czy powinniśmy tego uczyć stosując redukcje Karp czy redukcje Turinga? Uważam, że koncepcje kompletności i redukcji NP są czymś, czego powinien nauczyć się każdy kierunek informatyki. Jednak ucząc kompletności NP zauważyłem, że stosowanie redukcji Karp ma pewne …
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.