Pytania oznaczone «alternation»

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...

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...