Originally Posted by

**emakarov**

Basically, to decide k-IND it is enough to store k identifiers of vertices. One also needs an algorithm that searches through all k-subsets of vertices (i.e., writes each subset, one after another, into the space reserved for k vertices). Another subroutine that is needed is to check, for given k identifiers of vertices, if they are independent. If vertices are numbered in binary, then the space needed to store k identifiers is logarithmic w.r.t. input -- this is the most important part to check.