Pytania otagowane jako np-hardness

Pytania dotyczące twardości NP i kompletności NP.

2
W jaki sposób podejście geometryczne Mulmuleya-Sohoniego do wytwarzania dolnych granic unika tworzenia naturalnych dowodów (w sensie Razborowa-Rudicha)?
Dokładne sformułowanie tytułu należy do Ananda Kulkarniego (który zaproponował utworzenie tej strony). To pytanie zostało zadane jako przykładowe, ale jestem niesamowicie ciekawy. Wiem bardzo mało o geometrii algebraicznej, a tak naprawdę posiadam jedynie pobieżne, licencjackie rozumienie przeszkód występujących w pytaniu P / poli kontra NP (brak relatywizacji, brak algebrazowania, prawdopodobnie …
9
Redukcje z książki.
Jest to zgodne z „ Algorytmami z książki ”. Chociaż redukcje są również algorytmami, pomyślałem, że wątpliwe jest, aby pomyśleć o redukcji w odpowiedzi na pytanie o algorytmy z książki. Stąd osobne zapytanie! Wszelkie redukcje są mile widziane. Zacznę od bardzo prostej redukcji od osłony wierzchołków do multikutów na gwiazdach. …
8
Trudne problemy NP na ścieżkach
wszyscy wiedzą, że istnieje wiele problemów decyzyjnych, które są trudne NP na ogólnych wykresach, ale interesują mnie problemy, które są trudne NP, gdy podstawowy wykres jest ścieżką. Czy możesz mi pomóc w zebraniu takich problemów? Znalazłem już powiązane pytanie dotyczące trudnych NP problemów na drzewach .
4
Problemy, które w praktyce można rozwiązać w sposób sprzeczny z intuicją?
Niedawno przeszedłem przez bolesną zabawę polegającą na nieformalnym wyjaśnianiu koncepcji złożoności obliczeniowej młodemu utalentowanemu samoukiem, programistowi, który nigdy wcześniej nie odbył formalnego kursu algorytmów ani złożoności. Nic dziwnego, że wiele pojęć początkowo wydawało się dziwnych, ale miało sens w niektórych przykładach (PTIME, trudność, niezliczalność) , podczas gdy inne wydają się …
2
kompletność rozpoznania różnicy dwóch permutacji
Shor stwierdził w swoim komentarzu do odpowiedzi anonimowego łosia na to pytanie. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? , To jest -Complete do określenia różnicę dwóch permutacji. Niestety, nie widzę prostą redukcję od problemu sumy permutacji i warto mieć N P zmniejszenie -completeness dla problemu różnicy permutacji.NPNPNPNPNPNP …
4
Algorytmy DNA i kompletność NP
Jaki jest związek między algorytmami DNA a klasami złożoności określonymi za pomocą maszyn Turinga? Czym są pomiary złożoności, takie jak czas i przestrzeń w algorytmach DNA? Czy można je wykorzystać do rozwiązania problemów związanych z NP-zupełnymi, takich jak TSP, których maszyny von Neumann nie są w stanie rozwiązać w praktyce?
1
Grupowanie konsensusowe za pomocą ustawionej unii
Zadałem już to pytanie jakiś czas temu na MathOverflow , ale zgodnie z moją najlepszą wiedzą jest ono nadal otwarte, więc zamieszczam je ponownie w nadziei, że ktoś o nim usłyszy. Opis problemu Niech , i będą trzema partycjami w niepustych częściach (oznaczonych przez , i ) zestawu { }. …
1
Minimalne ukończenie wykresu nieparzystych cykli nieparzystych: czy jest trudne NP?
W moich badaniach pojawił się ostatnio następujący interesujący problem: INSTANCJA: Wykres .G ( V, E)G(V,E)G(V, E) ROZWIĄZANIE: Zakończenie akordu nieparzystego cyklu nieparzystego, zdefiniowane jako nadzbiór zestawu krawędzi tak że skompletowany wykres ma właściwość polegającą na tym, że każda krawędź w jest zawarta w bezciężkim cyklu nieparzystym.mi′E′E'miEEsol′( V, E′)G′(V,E′)G'(V, E')sol′G′G' POMIAR: …
3
Problemy, które są NP-zupełne w przypadku randomizacji lub redukcji P / poli.
W tym pytaniu wydaje się, że zidentyfikowaliśmy naturalny problem, który jest zupełny NP przy redukcjach losowych, ale być może nie przy redukcjach deterministycznych (chociaż zależy to od tego, które niesprawdzone założenia teorii liczb są prawdziwe). Czy znane są inne problemy? Czy istnieją jakieś naturalne problemy, które są NP-zupełne w przypadku …
4
Pozytywne uporządkowanie topologiczne, weź 3
Załóżmy, że mamy macierz n na n. Czy można zmienić kolejność wierszy i kolumn, tak aby uzyskać matrycę górnego trójkąta? To pytanie jest motywowane tym problemem: Pozytywne uporządkowanie topologiczne Pierwotny problem decyzyjny jest co najmniej tak trudny jak ten, więc wynik kompletności NP również by go rozwiązał. Edycja: Laszlo Vegh …
3
NP kompletne problemy graficzne na temat właściwości strukturalnych
(To pytanie jest trochę „ankietą”). Aktualnie pracuję nad problemem, w którym próbuję podzielić krawędzie turnieju na dwa zestawy, z których oba są wymagane do spełnienia niektórych właściwości strukturalnych. Problem „czuje się” bardzo trudne, a ja w pełni się spodziewać, że będzie N.P.NP\mathcal{NP} -complete.For jakiegoś powodu mam problemy ze znalezieniem nawet …
2
Czy problem zestawu wierzchołków sprzężenia zwrotnego można rozwiązać w czasie wielomianowym dla wykresów ograniczonych do 3 stopni?
Sprzężenie zwrotne Zestaw wierzchołków jest NP-kompletny dla ogólnych wykresów. Wiadomo, że jest NP-kompletny dla wykresów ograniczonych do stopnia 8 ze względu na redukcję z pokrycia wierzchołków. Artykuł w Wikipedii mówi, że jest on rozwiązany w czasie wielozakresowym dla grafów związanych ze stopniem 3 i jest NP-kompletny dla grafów związanych ze …
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.