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?

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