I had similar thoughts on this. It looks polynomial because he classified errors into certain groups and spread them across an axis which we implicitly think is a dimension. But it's not... as he says, "Along any one dimension we might have a combination of issues (i.e. multiple implementation bugs)". So looking at the grid and thinking you're at a single point is wrong... but so is thinking you could be any configuration of locations (you couldn't be at points (1, 1) and (2, 2), you also need to be at points (1, 2) and (2, 1), i.e. the set of points you're at is transitive). Thus this is a bad way to "enumerate the failure cases" and makes his notion of "adding a dimension" pretty unintuitive. It makes more sense to see every point of his dimensions as itself a dimension. Each of these dimensions could be either correct or incorrect, 1 or 0. So you're configuration could be visualized as a string of 1's and 0's. Thus, the number of possible configurations grows exponentially (2^n).