Pytania otagowane jako time-hierarchy

3
Uzasadnienie logarytmu f w twierdzeniu o hierarchii DTIME
Jeśli spojrzymy na twierdzenie o hierarchii DTIME, mamy dziennik z powodu narzutu w symulacji deterministycznej maszyny Turinga przez maszynę uniwersalną: DTIME(flogf)⊊DTIME(f)DTIME(flog⁡f)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) Nie mamy tego rodzaju kosztów ogólnych dla NTIME DSPACE. Podstawowe uzasadnienie wynika ze szczegółów dowodu, biorąc pod uwagę różnicę między symulatorami. Moje pytanie jest następujące: bez …
2
Hierarchia dla BPP a derandomizacja
W jednym zdaniu: czy istnienie hierarchii dla oznaczałoby jakiekolwiek wyniki derandomizacji?BPTIMEbP.T.jaM.mi\mathsf{BPTIME} Powiązane, ale niejasne pytanie brzmi: czy istnienie hierarchii dla implikuje jakieś trudne dolne granice? Czy rozwiązanie tego problemu uderza w znaną barierę w teorii złożoności?BPTIMEbP.T.jaM.mi\mathsf{BPTIME} Moim motywem do tego pytania jest zrozumienie względnej trudności (w odniesieniu do innych głównych …
2
Czy istnieje twierdzenie Hierarchia czasu dla PH?
Czy to prawda, że ​​w hierarchii wielomianowej występują problemy, które można rozwiązać w czasie O(nk)O(nk)O(n^k) (przez naprzemienną maszynę Turinga na pewnym poziomie hierarchii wielomianowej), których nie można rozwiązać w O(nk−1)O(nk−1)O(n^{k-1}) na żadnym poziomie hierarchia wielomianowa? Innymi słowy - czy istnieje twierdzenie o hierarchii czasu dla hierarchii wielomianowej, tak jak ma …
1
Hierarchie czasu w DSPACE (O (s)))
Twierdzenie o hierarchii czasu stwierdza, że ​​maszyny Turinga mogą rozwiązać więcej problemów, jeśli mają (wystarczająco) więcej czasu. Czy to w jakiś sposób się utrzymuje, jeśli przestrzeń jest asymptotycznie ograniczona? Jak DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) odnosi się do DTISP(f(n),O(s(n)))DTISP(f(n),O(s(n)))\textrm{DTISP}(f(n), O(s(n))) jeśli fgfg\frac{f}{g} rośnie wystarczająco szybko? Ja szczególnie zainteresowany w przypadku, s(n)=ns(n)=ns(n) = n …
1
Czy
Zdefiniuj jako klasę języków, które mogą być akceptowane przez (wielopasmową) maszynę Turinga w czasie f ( n ) + 1 . („ + 1 ” ma jedynie na celu uproszczenie notacji i uniknięcie pomyłek.) Zauważ, że nie ma O ( ⋅ ) wokół f ( n ) + 1 .D …
2
Co się stanie, jeśli poprawimy twierdzenia dotyczące hierarchii czasu?
f,gf,gf,gf(n)logf(n)=o(g(n))f(n)log⁡f(n)=o(g(n))f(n) \log f(n) = o(g(n))f , g f ( n + 1 ) = o ( g ( n ) )DTIME(f(n))⊊DTIME(g(n))DTIME(f(n))⊊DTIME(g(n)) DTIME(f(n)) \subsetneq DTIME(g(n))f,gf,gf,gf(n+1)=o(g(n))f(n+1)=o(g(n))f(n+1)=o(g(n))jest to NTIME(f(n))⊊NTIME(g(n)).NTIME(f(n))⊊NTIME(g(n)). NTIME(f(n)) \subsetneq NTIME(g(n)). Istnieje wiele (starych i aktualnych) wyników, które wykorzystują twierdzenia o hierarchii czasu do udowodnienia dolnych granic. Oto moje pytania: Co się …
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.