W teorii złożoności obliczeniowej PSPACE jest zbiorem wszystkich problemów decyzyjnych, które można rozwiązać za pomocą maszyny Turinga wykorzystującej wielomianową przestrzeń.
Formalna definicja Jeśli oznaczymy przez zestaw wszystkich problemów, które można rozwiązać za pomocą maszyn Turinga wykorzystujących przestrzeń dla pewnej funkcji o wielkości wejściowej wówczas możemy formalnie zdefiniować PSPACE jakoArora & Barak (2009) p. 81.
PSPACE jest ścisłym nadzbiorem zbioru języków kontekstowych.
Okazuje się, że pozwalając maszynie Turinga być niedeterministyczną, nie dodaje jej żadnej dodatkowej mocy. Ze względu na twierdzenie SavitchaArora & Barak (2009) p. 85. NPSPACE jest równoważne PSPACE, zasadniczo dlatego, że deterministyczna maszyna Turinga może symulować niedeterministyczną maszynę Turinga, nie wymagając dużo więcej miejsca (chociaż może zużywać znacznie więcej czasu)Arora & Barak (2009) p. 86..