Peut- on simuler des alternances

9

Soit la classe de langages décidée en alternant les machines de Turing qui s'arrêtent dans le temps f ( n ) en utilisant l'espace g ( n ) . Soit A A L T S P ( f ( n ) , g ( n ) ) la classe de langages décidée en alternant les machines de Turing qui cessent d'utiliser f (ATISP(f(n),g(n))f(n)g(n)AALTSP(f(n),g(n)) alternances et espace g ( n ) .f(n)g(n)

Ruzzo a prouvé que . Il a également montré que N C kA A L T S P ( log k n , log n ) N C k + 1 .NCk=ATISP(logkn,logn)NCkAALTSP(logkn,logn)NCk+1

Est ?NCk=AALTSP(logkn,logn)

argentpepper
la source

Réponses:

11

Bien entendu, les égalités et inclusions revendiquées dans la question ne s'appliquent qu'à l' uniforme . La classe A A L T S P ( log k n , log n ) est la même que l'uniforme A C k , la question est donc la même que de savoir si N C k = A C k .NCkAALTSP(logkn,logn)ACkNCk=ACk

En particulier, le cas implique que L est égal à N L et même L o g C F L , puisque N C 1LN LL o g C F LA C 1 . k=1LNLLogCFLNC1LNLLogCFLAC1

Jan Johannsen
la source