C'è qualche conseguenza dell'esistenza di $ \ Mathsf {PSPACE} $ - linguaggio sparso completo come con il teorema di Mahaney?

Question

Teorema di Mahaney afferma che l'esistenza di $ \ mathsf {np} $ -Complete Linguaggio sparse porterà a $ \mathsf {p= np} $ .C'è qualche risultato risultato riguardo lo stesso per la classe di complessità $ \ mathsf {pspace} $ , come "se c'è una $ \ MathSF {PSPACE} $ -COMPLETE LINGUA SPARSE, $ \ MATHSF {PP= PSPACE} $ "O lo stesso per qualsiasi altra classe di complessità all'interno $ \ MathSF {PSPACE} $ ?

Answer 1

Un risultato rapido è che $ PSPACE=SIGMA_2 $ .

Prima mostrare che $ PSPACE \ SOTETEQ P / Poly $ e come risultato $ PSPACE \ SorseTQ \ Sigma_2 $ (se trovare un'ingresso di una tabella di calcolo è in P / Poly, quindi è anche in $ \ Sigma_2 $ , dal momento che possiamo indovinare un circuito e Verifica localmente la sua correttezza come descritto qui ).

Per capire perché avere una lingua sparsa di Pspace-completa $ s $ mette PSPACE in P / Poly, data $ l \ in PSPACE $ , Let $ f $ essere una riduzione da $ l $ a < Span Class="Math-Container"> $ s $ . Si noti che se $ | f (x) | $ dipende solo da $ | x | $ , quindi < span class="container math"> $ l \ in P / poli $ poiché possiamo concatenare i circuiti per $ f $ e per $ s $ (che è in P / Poly a causa di essere sparsi). Per superare il fatto che $ f $ potrebbe variare nella lunghezza dell'output per la stessa dimensione di ingresso, si noti che su lunghezza $ n $ ingressi $ f $ può produrre output della lunghezza $ \ le n ^ c $ , così Dato $ x $ Possiamo prendere come suggerimento Tutto $ | x | ^ c $ circuiti per $ s $ su dimensioni in ingresso $ 0,1, ..., x | ^ c $ . Tra questi circuiti, abbiamo il circuito "giusto" che è in grado di determinare l'appartenenza di $ f (x) $ a $ S $ .