Abstract
Given a set H of binary vectors of length n, is there a listing of H so that every two successive vectors differ in a single coordinate? The problem of the existence of such a listing, which is called a Gray code of H, is known to be NP-complete in general. The goal of this paper is to specify boundaries between its intractability and polynomial decidability in terms of weights of vectors in H.