Pytania otagowane jako nondeterminism

3
Czy istnieje ograniczenie do gier typu „drzwi i płyta dociskowa”, które nie eksplodują długości rozwiązania?
Ten dokument stanowi dowód, że w grze z drzwiami i płytkami dociskowymi trudno jest ustalić, czy awatar (gracza) może dotrzeć do danego miejsca. Dowodzi tego redukcja z TQBF , a długość powstałych rozwiązań zależy wykładniczo od liczby uniwersalnych kwantyfikatorów we wzorze. Czy istnieje redukcja z maszyny NPSPACE do takiej gry, …
1
Jednolity sposób kwantyfikacji „rozgałęzień” w obliczeniach niedeterministycznych, probabilistycznych i kwantowych?
Obliczenia niedeterministycznej maszyny Turinga (NTM) są dobrze znane jako drzewa konfiguracji, zakorzenione w konfiguracji początkowej. Każde przejście w programie jest reprezentowane przez łącze ojciec-dziecko w tym drzewie. Podobne drzewa można również skonstruować do wizualizacji obliczeń maszyn probabilistycznych i kwantowych. (Należy zauważyć, że dla niektórych celów lepiej jest nie wyświetlać powiązanego …
2
Liczba minimalnych DFA wielkości co najwyżej ?
Niech będzie alfabetem wielkości i rozważmy minimalne DFA, których rozmiar jest ograniczony co najwyżej . Niech oznacza liczbę różnych takich minimalnych DFA.ΣΣ\Sigma222mmmf(m)f(m)f(m) Czy możemy znaleźć formułę zamkniętą dla ?f(m)f(m)f(m) Biorąc pod uwagę, że dla funkcją przejścia DFA o wielkości co najwyżej jest wykres. Ponieważ stopień węzłów jest ograniczony przez , …
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.