Marcus Schaefer: Deciding the K-Dimension is PSPACE-Complete. CCC 2000: 198-203