Pytania otagowane jako tradeoff

Czy niedeterminizm może przyspieszyć obliczenia deterministyczne? Jeśli tak to ile? Przyspieszając obliczenia deterministyczne przez niedeterminizm rozumiem wyniki formy: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Np. Coś takiego DTime(n2)⊆NTime(n)DTime(n2)⊆NTime(n)\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n) Jaki jest najbardziej znany wynik przyspieszenia obliczeń deterministycznych przez niedeterminizm? Co powiesz na ΣPkTime(n)ΣkPTime(n)\mathsf{\Sigma^P_kTime}(n) a nawet ATime(n)ATime(n)\mathsf{ATime}(n) zamiast NTime(n)NTime(n)\mathsf{NTime}(n) ? Załóżmy, że klasy …

14 cc.complexity-theory  nondeterminism  speed-up  alternation  tradeoff 

Jest to kontynuacja niedeterministycznego przyspieszenia obliczeń deterministycznych . Czy jest prawdopodobne, że niedeterminizm (lub bardziej ogólnie przemienność) pozwoliłby na ogólne kwadratowe przyspieszenie obliczeń deterministycznych? Czy są jakieś znane nieprawdopodobne konsekwencje czegoś takiego DTime(n2)⊆NTime(n)DTime(n2)⊆NTime(n)\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)?

9 cc.complexity-theory  nondeterminism  speed-up  alternation  tradeoff