I'm not sure the new formulation is correct either. It now states. An n-node simple graph (...) then we can encode the graph in polynomial space! But any n-no

I'm not sure the new formulation is correct either. It now states. An n-node simple graph (...) then we can encode the graph in polynomial space! But any n-node graph can be encoded in polynomial space. Maybe you mean to encode a 2^n node graph in polynomial space?