Pytania otagowane jako np-hard

problemy decyzyjne, które są co najmniej tak trudne, jak problemy NP-zupełne

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 …
2
Czy krzyżówki wyrażeń regularnych są trudne NP?
Pewnego dnia wygłupiałem się na tej stronie: http://regexcrossword.com/ i zastanawiałem się, jaki był najlepszy sposób rozwiązania tego problemu. Czy potrafisz rozwiązać następujący problem w czasie wielomianowym, czy jest to trudne NP? Biorąc pod uwagę siatkę NxM z N wyrażeniami regularnymi dla kolumn i M dla wierszy, znajdź dowolne rozwiązanie siatki, …
2
MIN-2-XOR-SAT i MAX-2-XOR-SAT: czy są NP-twarde?
Jaka jest złożoność MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} i MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Czy są w P? Czy są twarde NP? Aby sformalizować to dokładniej, pozwól Φ(x)=∧niCi,Φ(x)=∧jandoja,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, gdzie x=(x1,…,xm)x=(x1,…,xm)\mathbf{x} = (x_1,\dots,x_m) a każda klauzula CiCiC_i ma postać (xi⊕xj)(xi⊕xj)(x_i \oplus x_j) lub (xi⊕¬xj)(xi⊕¬xj)(x_i \oplus \neg x_j) . Problem 2-XOR-SAT2-XOR-SAT\text{2-XOR-SAT} polega na znalezieniu przypisania do xx\mathbf{x} które …
2
Czy kompletność coNP implikuje twardość NP?
Czy kompletność coNP implikuje twardość NP? W szczególności mam problem, który wykazałem, że jest kompletny coNP. Czy mogę twierdzić, że jest to trudne NP? Zdaję sobie sprawę, że mogę żądać twardości coNP, ale nie jestem pewien, czy ta terminologia jest standardowa. Nie mam nic przeciwko twierdzeniu, że jeśli problem NP-zupełny …
1
Twardość NP pokrycia kawałkami prostokątnymi (Google Hash Code 2015 Round Round)
Kodeks Hash 2015 Okrągły testowania Google ( oświadczenie problemem ) poprosił o następującym problemem: dane wejściowe: siatka z zaznaczonymi kwadratami, próg , maksymalny obszarT ∈ N A ∈ NM.M.MT.∈ N.T.∈N.T \in \mathbb{N}A ∈ NZA∈N.A \in \mathbb{N} Wydajność: największa powierzchnia całkowita zestawu rozłącznych prostokątów o współrzędnych całkowitą w tak, że każdy …
1
Udowodnienie, że diagnoza ukierunkowanego wykresu jest trudna do przeprowadzenia
Mam zadanie domowe, od którego walę głową od jakiegoś czasu i byłbym wdzięczny za wszelkie wskazówki. Chodzi o wybranie znanego problemu, którego kompletność NP jest udowodniona, i skonstruowanie redukcji z tego problemu do następującego problemu, który nazywam DGD (diagnostyka grafu ukierunkowanego). Problem Instancja projekcie wytycznych składa się z wierzchołkami V …
1
Czy kompletne zestawy NP są tworzone z dwóch innych zestawów tylko wtedy, gdy co najmniej jeden jest twardy NP?
To pytanie jest nieco odwrotne do poprzedniego pytania dotyczącego zestawów utworzonych z operacji na zestawach na zestawach NP-complete: Jeśli zbiór wynikający ze związku, przecięcia lub iloczynu kartezjańskiego dwóch rozstrzygalnych zbiorów L1L1L_1 i jest NP-kompletny, to czy przynajmniej jeden z koniecznie NP-twardy? Wiem, że oba nie mogą być w P (zakładając, …
4
Czy znalezienie świadka może być trudne, nawet jeśli już wiemy, że istnieje?
Typowe przykłady problemów trudnych dla NP (klika, 3-SAT, osłona wierzchołków itp.) Są tego typu, w którym nie wiemy, czy odpowiedź brzmi „tak” czy „nie” wcześniej. Załóżmy, że mamy problem, w którym wiemy, że odpowiedź brzmi tak, a ponadto możemy zweryfikować świadka w czasie wielomianowym. Czy wtedy zawsze możemy znaleźć świadka …
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 …
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.