It's known that K-CLIQUE is a NP-Complete problem.
The question is, what am I missing in the following non-deterministic algorithm, which should decide the K-CLIQUE problem in O(logn) space.
(It must be wrong, otherwise K-CLIQUE which is proven to be NP-Complete would be in NL, therefore NP=NL, and that's not proven.)
1) Guess a vertex – x, (as a delegate for the potential K-group of
vertices).
2) Verify that x has at most k neighbor vertices
2.1) Otherwise, return F
3) For each neighbor x'
3.1) For each neighbor x''
3.1.1) Verify that the edge (x', x'') exists.
3.1.1.1) Otherwise, return F
4) return T
Complexity:
1) The delegate x is encoded with O(logn) space.
2) In each iteration only x and one of his neighbors are on the working tape – 2logn -> O(logn).
(The validation if an edge exists is done by reading the input tape and shouldn't affect the overall space complexity)
3) In order to iterate over the neighbors of x, only 2 'pointers' to E are needed. – O(logn), plus the verification is again reading the input tape and shouldn't affect the overall complexity.
What's wrong with the analysis above?
Best Answer
Your step 2 is not right: $x$ could belong to a clique of size $k$ but have more than $k - 1$ neighbours. To find a clique of size $k$ containing $x$ you need to search through all subsets of size $k - 1$ of the neighbours of $x$.