We discovered a serious error in one of our previous submissions to ECCC and wish to make sure that this mistake is publicly known.

The main argument of the report TR06-133 is in error. The paper claims to prove the result of the title by reduction from the (Exists,k)-pebble game, shown to be EXPTIME-complete by Kolaitis and Panttaja. This note shows that the principal lemma is incorrect by providing a simple counter-example.