Pytania otagowane jako np

NP oznacza niedeterministyczny czas wielomianowy.

1
Najbardziej znane wspólne pojemniki dla / przez NP i Parity-P?
Parzystość-P jest zbiorem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko parzystą liczbę lub nieparzystą liczbę ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji). Zatem Parity-P jest w zasadzie PP „s karłowate młodsze rodzeństwo: podczas liczy PP czy liczba przyjmujących ścieżkach NP-maszyna jest większość, czy nie ( …
2
Twardość sparametryzowanego CLIQUE?
Niech 0≤p≤10≤p≤10\le p\le 1 i rozważmy problem decyzyjny Klika P Wejście: całkowita s , wykres G z T wierzchołki krawędzie Pytanie: sposób zawierać klika na co najmniej wierzchołki?pp_p sssGGGtttGs⌈p(t2)⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil GGGsss Instancja CLIQUE zawiera proporcję spośród wszystkich możliwych krawędzi. Wyraźnie CLIQUE jest łatwy dla niektórych wartości . CLIQUE zawiera …
2
(Jak) Czy możemy odkryć / przeanalizować problemy NP przy braku modelu obliczeniowego Turinga?
Z czysto abstrakcyjnego punktu widzenia rozumowania matematycznego / obliczeniowego (jak) można nawet odkryć lub wyjaśnić problemy takie jak 3-SAT, suma częściowa, podróżny sprzedawca itp.,? Czy bylibyśmy w stanie w jakikolwiek sensowny sposób uzasadnić je tylko z funkcjonalnego punktu widzenia? Czy to w ogóle możliwe? Zastanawiam się nad tym pytaniem wyłącznie …
1
pełny problem z quasi-wielomianem związanym z liczbą rozwiązań
FewP to klasa z wielomianem ograniczonym liczbą rozwiązań (w wielkości wejściowej). Tam nie jest znana -Complete problem . Interesuje mnie, jak daleko możemy rozciągnąć tę obserwację.N P f e w PNPNPNPNPNPNPfewPfewPfewP Czy istnieje jakiś naturalny problem z uzupełnieniem z quasi-wielomianową górną granicą liczby rozwiązań (świadków)? Czy istnieje powszechnie przyjęte przypuszczenie, …
1
Czy kompletność PSPACE oznacza twardość aproksymacyjną?
W komentarzu w innym poście z cstheorySE wspomniano, że kompletność PSPACE implikuje twardość APX. Czy ktoś może wyjaśnić / udostępnić referencję? Czy to jest „ciasne”? (tj. czy istnieją problemy kompletne z PSPACE, których problem optymalizacji dopuszcza stałe przybliżanie współczynnika w czasie wielopunktowym? Co z kompletnością dla pewnego poziomu PH? Czy …
1
Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany?
Pytanie przyszło mi do głowy, kiedy otrzymałem odpowiedź Dany Moshkovitz na inny temat . Niech będzie językiem NP , a będzie odpowiednią relacją NP . Wiemy, że istnieje pewien wielomian taki, że:LLLRLRLR_Lppp ∀x∈L,,∃w∈0,1p(|x|)(x,w)∈RL∀x∈L,,∃w∈0,1p(|x|)(x,w)∈RL\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L Powyższe stwierdzenie wymaga tylko istnienia …
1
Czy występują problemy z „NP-Intermediate-Complete”?
Załóżmy, że P NP.≠≠\ne Twierdzenie Ladnera mówi, że istnieją problemy pośrednie NP (problemy w NP, które nie są ani w P, ani w NP-Complete). Znalazłem w Internecie kilka zawoalowanych odniesień, które sugerują (myślę), że istnieje wiele „poziomów” wzajemnie redukowalnych języków w ramach NPI, które zdecydowanie nie wszystkie się zlewają. Mam …
2
Euklidesowy TSP w NP i złożoność pierwiastka kwadratowego
W notatkach z wykładu Oli Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf mówi się, że nie wiemy, czy Euclidean TSP jest w NP: Powodem jest to, że nie wiemy, jak skutecznie obliczać pierwiastki kwadratowe. Z drugiej strony jest ten artykuł Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123, który mówi, że jest NP-kompletny, co oznacza również, że jest w NP. Chociaż …
3
NP-pełna właściwość graficzna, która jest dziedziczna, ale nie addytywna?
Właściwość wykresu jest nazywana dziedziczną, jeśli zostanie zamknięta w odniesieniu do usuwania wierzchołków (tj. Wszystkie indukowane podgrupy dziedziczą właściwość). Właściwość graf nazywa się addytywną, jeśli jest zamknięta w odniesieniu do przyjmowania rozłącznych związków. Nie jest trudno znaleźć właściwości dziedziczne, ale nie addytywne. Dwa proste przykłady: \;\;\;(1) Wykres jest kompletny. \;\;\;(2) …
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.