Pytania otagowane jako np-hardness

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

1
Produkt pośredni
Problem podziału jest słabo NP-zupełny, ponieważ ma wielomianowy (pseudo-wielomianowy) algorytm czasowy, jeśli wejściowe liczby całkowite są ograniczone przez jakiś wielomian. Jednak 3-partycja jest silnym problemem NP-zupełnym, nawet jeśli wejściowe liczby całkowite są ograniczone przez wielomian. Zakładając, , Czy możemy udowodnić, że pośrednie problemy NP-zupełne muszą istnieć? Jeśli odpowiedź brzmi „tak”, …
1
Złożoność dominującego problemu w określonych podklasach wykresów akordowych
Interesuje mnie złożoność problemu dominującego zestawu (DSP) w niektórych określonych klasach grafów, które są podklasami grafów akordowych . Wykres jest nieukierowanym wykresem ścieżki, jeśli jest to wykres przecięcia wierzchołków rodziny ścieżek w jakimś niekierowanym drzewie. Niech UP będzie klasą niekierowanych grafów ścieżek. Wykres jest grafem EPT, jeśli jest to wykres …
3
Klasy wykresów z łatwym cyklem hamiltonowskim, ale z TSP NP-twardym
Hamiltona Cykl Problem (HC) polega na znalezieniu cykl, który przechodzi przez wszystkie wierzchołki w danym undirected wykresu. Problem komiwojażera (TSP), polega na znalezieniu się cykl, który przechodzi przez wszystkie wierzchołki w danej krawędzi wykresu ważonych minimalizuje całkowitą odległość, mierzoną przez sumę mas krawędzi w cyklu. HC jest szczególnym przypadkiem TSP …
1
Czy „Czy permutacja jest automorfizmem grafu w moim zestawie?” NP-kompletny?
Załóżmy, że mamy zestaw S grafów (wykresy skończone, ale ich nieskończona liczba) i grupę P permutacji, która działa na S. Instancja: permutacja pw P. Pytanie: Czy istnieje wykres g w S, który dopuszcza automorfizm p? Czy ten problem NP-zupełny dla niektórych zestawów S? Łatwo byłoby sprawdzić, czy wykres dopuszcza permutację …
2
Partycja wolna od H.
To jest pytanie, zainspirowany problemu cięcia H-darmo . Biorąc pod uwagę wykres, podział jego zbioru wierzchołków na r części V 1 , V 2 , … , V r jest wolny od H, jeśli G [ V i ] nie indukuje kopii H dla wszystkich i , 1 ≤ i …
4
Czy możemy szybko wygenerować idealnie jednolicie mod 3 lub rozwiązać problem NP?
Szczerze mówiąc, nie wiem zbyt wiele o tym, jak generowana jest liczba losowa (komentarze są mile widziane!), Ale załóżmy następujący model teoretyczny: Możemy uzyskać liczby całkowite jednolicie losowe z a naszym celem jest wyprowadza liczbę całkowitą jednolicie losową z [1,3].[ 1 , 2 n ][1,2n][1,2^n] Oto proste rozwiązanie, którego oczekiwany …
2
Cykl hamiltonowski na wykresach bez małych cykli
Odpowiadając na to pytanie w cstheory , (nieformalnie) udowodniłem w locie następujące twierdzenie: Twierdzenie : Dla dowolnego ustalonego sonda cyklu Hamiltoniana pozostaje NP-kompletna, nawet jeśli jest ograniczona do płaskich dwustronnych grafów niekierowanych o maksymalnym stopniu 3, które nie zawierają cykli o długości ≤ l .l≥3l≥3l \geq 3≤l≤l\leq l Wydaje się …
1
Wydajny algorytm dla istnienia permutacji z sekwencją różnic?
To pytanie jest motywowane tym postem. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? oraz moje zainteresowanie obliczeniowymi właściwościami permutacji. Sekwencja różnic permutacji π liczb 1 , 2 , … n + 1 jest tworzona przez znalezienie różnicy między każdą dwiema sąsiednimi liczbami w permutacji π . Innymi słowy, …
1
Jak trudna jest binarna łamigłówka Sudoku?
Sudoku jest dobrze znaną łamigłówką, która jest kompletna NP. Sudoku Binarne to wariant, który dopuszcza tylko cyfry i 1 . Zasady są następujące.000111 Każdy wiersz i każda kolumna musi zawierać równą liczbę zer i jedynek. Każdy wiersz i każda kolumna jest unikalny. Żaden wiersz ani kolumna nie zawiera kolejnych potrójnych …
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.