Ograniczona wersja problemu Clique?

Rozważ następującą wersję problemu Kliki, w której dane wejściowe mają rozmiar a my poprosimy o znalezienie kliki o rozmiarze . Ograniczeniem jest to, że procedura decyzyjna nie może zmienić wykresu wejściowego na żadną inną reprezentację i nie może użyć żadnej innej reprezentacji do obliczenia swojej odpowiedzi, oprócz dodatkowych bitów poza grafem wejściowym. Dodatkowe bity można wykorzystać na przykład w algorytmie brutalnej siły, aby śledzić status wyczerpującego wyszukiwania kliki, ale procedura decyzyjna jest mile widziana, aby użyć ich w jakikolwiek inny sposób, który nadal decyduje o problemie. $n$ $k$ $\log(n^k)$

Czy w tym momencie wiadomo o złożoności tego zjawiska? Czy wykonano jakieś prace nad innymi ograniczeniami Kliki, a jeśli tak, czy możesz skierować mnie do takiej pracy?

complexity-theory time-complexity

— Nieśmiała osoba
źródło

Czy chcesz, aby stała w była taka sama jak wielkość kliki ?

k

$k$

\lg n^{k}

$\lg n^k$

k

$k$

— Lucas Cook

@LucasCook Tak.

— ShyPerson

Brzmi to tak, jakbyś pytał, czy problem kliki NP-complete można rozwiązać w przestrzeni logarytmicznej. Używając maszyn Turinga, jedna taśma jest tylko do odczytu i przechowuje wykres wejściowy. Druga taśma jest ograniczone tak, że nie znajduje się w przestrzeń dostępna dla pewnej stałej . Klasa problemów możliwych do rozwiązania w tym modelu jest znana jako , deterministyczna przestrzeń logarytmiczna. (Zobacz wikipedia lub w złożonym zoo ) $c \lg n$ $c$ $L$

Nie wiadomo, czy , ale pozytywna odpowiedź oznaczałaby, że , więc (prawie na pewno?) Nie znajdziesz odpowiedzi. i implikuje , co oznacza . $\mathrm{CLIQUE} \in L$ $P = NP$ $L \subseteq P \subseteq NP$ $\mathrm{CLIQUE} \in L$ $\mathrm{CLIQUE} \in P$ $P = NP$

Edytuj w przypadku, gdy źle zinterpretowałem problem:

Jeśli masz zamiar, aby w było takie samo jak rozmiar kliki (tj. Ilość skal pamięci z wejściem ), to istnieje prosty algorytm brutalnej siły: możesz zapętlić wszystkie możliwe zestawy węzłów i sprawdź, czy tworzą one klik. Punktem wyjścia do poszukiwania lepszych rozwiązań mogą być odniesienia do [1]. $k$ $\lg n^k = k \lg n$ $k$ $k$ $k$ $k$

[1] Virginia Vassilevska, „Skuteczne algorytmy dla problemów klikowych” link pdf

— Lucas Cook
źródło

@ShyPerson Ok. Łańcuch wejściowy jest często niezmienny w modelach z ograniczoną przestrzenią (takich jak podliniowe kosmiczne bazy TM w lub ), więc może to być dobre miejsce do patrzenia. Nie jestem pewien formalnego sposobu na powiedzenie, że „nie można zrobić innej reprezentacji” poza ograniczeniem przestrzeni. Jeśli pozwolę sobie na miejsce do wykonania kolejnej kopii , co dokładnie stanowi inną reprezentację? Co się stanie, jeśli „przypadkowo” zbuduję wystarczającą reprezentację dla wykresu szczególnie rzadkiego lub ściśliwego?

L

$L$

N L

$NL$

G

$G$

— Lucas Cook

k C L I Q U E

$\mathrm{kCLIQUE}$ nie jest NP-kompletny! (chyba że )

P = N P

$\mathrm{P}= \mathrm{NP}$

— Alex ten Brink

@AlextenBrink Czy masz na myśli, że kCLIQUE jest problemem funkcji? Zmieniłem nazwę na CLIQUE powyżej (zawsze je mylę!), Ale dziwne jest dla mnie stwierdzenie, że kCLIQUE jest w NP, jeśli masz na myśli problem z funkcją.

— Lucas Cook

Znaczący searchproblem w tym przypadku.

— Lucas Cook

k C L I Q U E

$\mathrm{kCLIQUE}$ to problem dla ustalonego , podczas gdy ma jako część danych wejściowych. Sprawdzając wszystkie podgrupy wielkości , masz algorytm , który jest wielomianowy, jeśli jest stały, ale superpolinomalny, jeśli na przykład .

C L I Q U E

$\mathrm{CLIQUE}$

k

$k$

C L I Q U E

$\mathrm{CLIQUE}$

k

$k$

k

$k$

O (n^{k})

$O(n^k)$

k

$k$

k = Θ (n)

$k=\Theta(n)$

— Alex ten Brink