The question is: What is the smallest complexity class in which the following problem is contained: Given a graph with $n$ nodes, Is there independent set of size of at least $n-10$?
I have a little difficulty to understand the meaning of being in ${\sf L}$ and examine problems in a correct way for deciding if they are in ${\sf NL}$ or ${\sf L}$
First I know that for being in ${\sf NL}$ I need to provide a verifier for a Turing machine which uses only $O(\log n)$ space on its working tape- So I wonder- I can give as a verifier this set of nodes to be independent set as requested, but how does the checking work? Can it go to all the lists of the pointers to the neighbors of each node , and for every node to check whether all the other nodes in the set given as independent set is not on that list- Is this considered of not using any space and I only need to count the nodes in the list that fulfill the requirement and therefore use only $O(\log n)$ space? Is this correct? Is there a way to prove that the problem is in ${\sf L}$?