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.

2
Gęsty NP pełny język oznacza P = NP
Mówimy, że język jest gęsty, jeśli istnieje wielomian taki, że dla wszystkichInnymi słowy, dla dowolnej długości istnieje tylko wielomianowo wiele słów o długości , które nie są wJ⊆Σ∗jot⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|jotdo∩Σn|≤p(n) |J^c \cap \Sigma^n| \leq p(n)n∈N.n∈N..n \in \mathbb{N}.nnnnnnJ.jot.J. Problem, który obecnie badam, wymaga przedstawienia następujących informacji Jeśli istnieje gęsty język , …
1
NP-zupełny problem z wielomianową liczbą tak-wystąpień?
Mam wrażenie, że dla każdego problemu NP-zupełnego, dla nieskończenie wielu rozmiarów wejściowych , liczba wystąpień tak we wszystkich możliwych wejściach wielkości jest (przynajmniej) wykładnicza w n .nnnnnnnnn Czy to prawda? Czy można to udowodnić (prawdopodobnie tylko przy założeniu, że P.≠ N.P.P.≠N.P.P\neq NP )? A może sztucznie możemy znaleźć problem, w …
1
Pokrycie siatki prostokątami
Mamy siatkę . Mamy zbiór prostokątów na tej siatki, każdy prostokąta może być przedstawiony jako -by- binarna matryca . Chcemy pokryć siatkę tymi prostokątami.N 1 N 2 RN1×N2N1×N2N_1 \times N_2N1N1N_1N2N2N_2RRR Czy wersja decyzyjna tego zestawu obejmuje problem NP-zupełny? Dane wejściowe: Collection prostokątów na siatce (rozmiar wejściowy: ) iN 1 N …
3
Minimalny rozmiar zawarcia DAG w nowy DAG
Mamy DAG. Mamy funkcję na węzłach (luźno mówiąc, numerujemy węzły). Chcielibyśmy utworzyć nowy ukierunkowany wykres z tymi zasadami:fa: V→ N.F:V→NF\colon V\to \mathbb N Tylko węzły o tym samym numerze można zawrzeć w tym samym nowym węźle. . (Jednak .)fa( x ) ≠ F.( y) ⇒ x′. Y′F(x)≠F(y)⇒x′≠y′F(x) \neq F(y) \Rightarrow …
3
Jeśli P = NP, dlaczego
Najwyraźniej, jeśli , wszystkie języki w z wyjątkiem i byłyby -kompletne.P = N PP=NP{\sf P}={\sf NP}P.P{\sf P}∅∅\emptysetΣ∗Σ∗\Sigma^*N P.NP{\sf NP} Dlaczego w szczególności te dwa języki? Czy nie możemy zredukować do nich żadnego innego języka w , wysyłając je podczas przyjmowania lub odrzucania?P.P{\sf P}
1
Najszybsza znana złożoność kombinatorycznego algorytmu ILP?
Zastanawiam się, co jest najbardziej znany algorytm, jeśli chodzi o Big- notacji, aby rozwiązać Programowanie Integer Linear?OOO Wiem, że problem jest , więc nie oczekuję niczego wielomianowego. Wiem, że istnieje wiele heurystyk, które są wykorzystywane w praktycznych zastosowaniach, takich jak CPLEX, ale bardziej interesuje mnie formalna, w najgorszym przypadku złożoność …
1
Warunki płaskości dla Planar 1-in-3 SAT
Planar 3SAT jest kompletny z NP. Płaska instancja 3SAT jest instancją 3SAT, dla której wykres zbudowany przy użyciu następujących reguł jest płaski: dodaj wierzchołek dla każdegoxixix_i i xi¯xi¯\bar{x_i} dodać wierzchołek dla każdej klauzuli CjCjC_j dodaj krawędź dla każdej pary (xi,xi¯)(xi,xi¯)(x_i,\bar{x_i}) dodaj krawędź z wierzchołka (lub ¯ x i ) do …
2
Czy każdy problem NP ma wielocząsteczkowy preparat ILP?
Ponieważ całkowite programowanie liniowe jest zakończone NP, występuje zmniejszenie Karp z dowolnego problemu w NP. Pomyślałem, że to sugeruje, że zawsze istnieje wielomianowa formuła ILP dla dowolnego problemu w NP. Ale widziałem artykuły na temat konkretnych problemów związanych z NP, w których ludzie piszą takie rzeczy, jak: „to jest pierwszy …
1
Przybliżenie minimalnej przepustowości drzew binarnych
Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami. Problem decyzyjny jest NP-zupełny nawet dla drzew binarnych. Wyniki złożoności dla minimalizacji przepustowości. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, nr 3, 1978 . …
2
Skrócenie czasu między ILP a SAT?
Tak więc, jak wiadomo, problem decyzyjny ILP 0-1 jest NP-zupełny. Pokazanie tego w NP jest łatwe, a pierwotna redukcja pochodziła z SAT; od tego czasu wykazano, że wiele innych problemów z NP-Complete ma formulacje ILP (które działają jako redukcje tych problemów do ILP), ponieważ ILP jest bardzo przydatna ogólnie. Redukcje …
1
Znalezienie optymalnej sekwencji pytań w celu zminimalizowania całkowitego czasu studenta
Załóżmy, że na uniwersytecie jest sesja szkoleniowa. Mamy zestaw pytań i zestaw studentów . Każdy uczeń ma wątpliwości w pewnym podzbiorze pytań, tj. Dla każdego ucznia , niech będzie zbiorem pytań, w które uczeń ma wątpliwości. Załóżmy, że i .kkkQ={q1…qk}Q={q1…qk}Q = \{ q_1 \ldots q_k \}nnnS={s1…sn}S={s1…sn}S = \{ s_1 \ldots …
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.