Version restreinte du problème Clique?

Considérons la version suivante du problème Clique où l'entrée est de taille et on nous demande de trouver une clique de taille k . La restriction est que la procédure de décision ne peut pas transformer le graphe d'entrée en toute autre représentation et ne peut utiliser aucune autre représentation pour calculer sa réponse, autre que log ( n k ) bits supplémentaires au-delà du graphe d'entrée. Les bits supplémentaires peuvent être utilisés par exemple dans l'algorithme de force brute pour garder une trace de l'état de la recherche exhaustive d'une clique, mais la procédure de décision est la bienvenue pour les utiliser de toute autre manière qui décide toujours du problème.$n$$k$$\log(n^k)$

Est-ce que quelque chose est connu à ce stade sur la complexité de cela? Y a-t-il eu un travail sur d'autres restrictions de Clique, et si oui, pourriez-vous me diriger vers un tel travail?

On dirait que vous demandez si le problème de clique NP-complet peut être résolu dans l'espace logarithmique. En utilisant les machines Turing, une bande est en lecture seule et stocke le graphique d'entrée. L'autre bande est délimitée de manière à ce qu'il y ait un espace disponible pour une constante c . La classe de problèmes pouvant être résolus dans ce modèle est connue sous le nom de L , espace logarithmique déterministe. (Voir wikipedia ou dans le zoo de la complexité )$c \lg n$$c$$L$

On ne sait pas si , mais une réponse positive impliquerait que P = N P , donc vous (presque sûrement?) Ne trouverez pas de réponse. L ⊆ P ⊆ N P et C L I Q U E ∈ L implique C L I Q U E ∈ P , ce qui implique P = N $\mathrm{CLIQUE} \in L$$P = NP$$L \subseteq P \subseteq NP$$\mathrm{CLIQUE} \in L$$\mathrm{CLIQUE} \in P$$P = NP$ .

Modifier au cas où j'aurais mal interprété le problème:

Si vous prévoyez que le dans lg n k = k lg n est le même que la taille de la clique k (c'est-à-dire la quantité de mémoire échelles avec l'entrée k ), alors il y a un algorithme de force brute simple: vous pouvez parcourir tous les ensembles possibles de k nœuds et vérifier s'ils forment une k -clique. Un point de départ pour rechercher de meilleures solutions pourrait être les références de [1].$k$$\lg n^k = k \lg n$$k$$k$$k$$k$

[1] Virginia Vassilevska, "Des algorithmes efficaces pour les problèmes de clique" lien pdf