Pytania otagowane jako np-hardness

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

2
Złożoność ukrytej łamigłówki wielokątów na kwadratowych siatkach?
Hiroimono jest popularną łamigłówką . Interesuje mnie złożoność obliczeniowa powiązanej układanki.N.P.NPNP Problemem jest: Dane wejściowe : Biorąc pod uwagę zestaw punktów na siatce kwadratowej x i liczbie całkowitejn knnnnnnkkk Pytanie : Czy istnieje wielokąt prostoliniowy (jego boki równoległe do osi lub ) taki, że liczba punktów na rogach wielokąta wynosi …
2
NP-kompletne warianty nierozwiązywalnych problemów?
Przykłady ograniczone -Complete wariantów nierozstrzygalnych zestawach:N.P.NPNP Ograniczony problem zatrzymania = { | Maszyna NTM M zatrzymuje się i przyjmuje x w ciągu t kroków}( M, x , 1t)(M,x,1t)(M, x, 1^t)M.MMxxxttt Ograniczone płytki = { | jest płytki kwadratu o powierzchni t 2 za pomocą płytek z T }( T, 1t)(T,1t)(T, …
1
Jakie są złożoności następujących podzbiorów SAT?
Załóżmy, żeP.≠ N.P.P≠NPP \neq NP Do tetracji użyj następującego zapisu (tj. ).jazaia{}^iajaa = aza⋅⋅⋅zaja razyia=aa⋅⋅⋅a⏟i times{}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}} | x | jest wielkością instancji x. Niech L będzie językiem,L |fa( i ) ≤ | x | &lt; g( i ):={x∈L | ∃i∈N, f(i)≤|x|&lt;g(i)}L|f(i)≤|x|&lt;g(i):={x∈L | ∃i∈N, f(i)≤|x|&lt;g(i)}L|_{f(i)\leq |x| < …
1
Twardość problemu z ograniczonym układem gwiezdnym?
Układ gwiazda rodziny n podzbiorów n-elementów przedstawionych . System położony jest graficznym, jeżeli jest jakiś wykres tak, że jest rodzina sąsiedztwie wierzchołków w . To jest kompletne, aby zdecydować, czy dany układ gwiezdny jest graficzny.S G ( V , E ) F G N PFFFSSSG(V,E)G(V,E)G(V,E)FFFGGGNPNPNP Jaka jest minimalna wystąpienie każdego …
3
Trudność ze znalezieniem co najwyżej słowa
Opis problemu: Pozwolić MMM być (potencjalnie niedeterministycznym) automatem wypychającym i pozwól AA\cal Abyć jego alfabetem wejściowym. Czy jest jakieś słowo?w∈A∗w∈A∗w \in \cal A^* św |w|≤k|w|≤k|w| \leq k które jest akceptowane przez MMM ? Czy ten problem NP-jest kompletny? Czy zostało to zbadane? Czy istnieje algorytm pozwalający znaleźć takie słowo?
1
Najbardziej znane asymptotyczne rozmiary PCP / 3-SAT
Jakie są najbardziej znane asymptotyczne górne granice wielkości dowodów probabilistycznie sprawdzalnych? Idealnie szukam współczesnej ankiety dotyczącej tego szerokiego pytania, ale jeśli jej nie ma, szczególnie interesuje mnie niedopuszczalność 3-SAT. Niech 7/8 + ε-3-SAT będzie 3-SAT z obietnicą, że jeśli 7/8 + ε część klauzul jest zadowalająca, to instancja jest zadowalająca. …
1
Co wiadomo na temat twardości wskaźnika chromatycznego dla ograniczonych klas grafów?
Jest ładny papier z 1991 roku, który zawiera trzy diagramy dotyczące różnych rodzin klas grafów, pokazujące, co wiadomo na temat twardości wyznaczania dla nich indeksu chromatycznego. Czy są odtąd jakieś wiadomości na ten temat? Najbardziej interesuje mnie to, co wiadomo na temat wykresów z ograniczoną liczbą chromatyczną. Moja ciekawość została …
1
Złożoność homomorfizmu digrafa w cyklu zorientowanym
Biorąc pod uwagę stałą skierowane wykres (digrafu) The -COLORING problem decyzyjny pyta czy digrafu wejście ma homomorfizm do . (Homomorfizmem od do jest odwzorowaniem od do , która chroni łuki, to znaczy, gdy jest łukiem , a jest łukiem )DDDDDDGGGDDDGGGDDDfffV(G)V(G)V(G)V(D)V(D)V(D)uvuvuvGGGf(u)f(v)f(u)f(v)f(u)f(v)DDD Klasa problemów COLORING jest silnie związana z hipotezą dychotomii dla …
1
Czy 1-w-3 SAT pozostaje NP-twardy, nawet jeśli każda zmienna występuje zarówno pozytywnie, jak i negatywnie?
Standardowy problem 1-w-3 SAT (lub XSAT lub X3SAT) to: Instancja : formuła CNF z każdą klauzulą ​​zawierającą dokładnie 3 literały Pytanie : czy istnieje zadowalające ustawienie przypisania dokładnie 1 literał na klauzulę prawda? Problem jest NP-zupełny i pozostaje trudny, nawet jeśli żadna zmienna nie zostanie zanegowana. Zastanawiam się, czy problem …
1
Podział krawędzi na tęczowe trójkąty
Zastanawiam się, czy następujący problem jest trudny NP. Wprowadź: prosty wykres i kolorowanie krawędzi ( nie weryfikuje żadnej konkretnej właściwości).G = ( V, E)G=(V,E)G = (V,E)fa: E→ { 1 , 2 , 3 }f:E→{1,2,3}f : E \to \{1,2,3\}faff Pytanie: czy można podzielić na trójkąty , tak aby każdy trójkąt miał …
1
Dopasowanie masy „sprawiedliwe”
Interesuje mnie wariant maksymalnego dopasowania wagi na wykresie, który nazywam „maksymalnym uczciwym dopasowaniem”. Załóżmy, że wykres jest pełny (tj E=V×VE=V×VE=V\times V) Ma liczbę nawet wierzchołków, a masa jest podawana przez funkcję zysk . Biorąc pod uwagę pasujące , oznacz przez zysk krawędzi jest dopasowany.p:(V2)→Np:(V2)→Np:{V\choose 2}\to \mathbb NMMMM(v)M(v)M(v)vvv Pasujące jest sprawiedliwym …
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.