hogy P-ben van mondjuk egy kanonikusan PSPACE-beli eldöntési algoritmust használó nyelv. Ez erős eredmény.

 

 

buki,

 

közben eszembe jutott egy szép tétel, ami érdekelhet: a CS nyelvek szóproblémája PSPACE-teljes.

 

Így, ha polinom algoritmust találnánk a CS nyelvek szóproblémájának eldöntésére, az P=NP-t is jelentené.

 

Egyúttal az is igaz, hogy IP=PSPACE, vagyis interaktív prokotokollal eldönthetőek a CS nyelvek (Shamir tétele).

 

Végül igaz Savitch tétele: PSPACE=NPSPACE, vagyis a nemdeterminnizmus ebben nem számít.