Pytania otagowane jako tradeoff

3
Niedeterministyczne przyspieszenie obliczeń deterministycznych
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 …

1
Czy możliwe jest zwiększenie kwadratowego niedeterminizmu przyspieszenia obliczeń deterministycznych?
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)?
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.