Co się stanie, jeśli poprawimy twierdzenia dotyczące hierarchii czasu?

10

$f,g$ $f(n) \log f(n) = o(g(n))$

D T I M E (f (n)) ⊊ D T I M E (g (n))

$DTIME(f(n)) \subsetneq DTIME(g(n))$

f, g

$f,g$

f (n + 1) = o (g (n))

$f(n+1)=o(g(n))$ jest to

N T I M E (f (n)) ⊊ N T I M E (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ę stanie, jeśli uda nam się udowodnić lepszy wynik dla przypadku deterministycznego lub niedeterministycznego?
Jeśli możemy udowodnić, że istnieje luka między deterministyczną hierarchią czasu a niedeterministyczną hierarchią czasu, czy oznacza to, że $P \neq NP$ ?

— Marc Bury
źródło

Tylko mała notatka. W przypadku maszyn Turinga z taśmą

o

k > 2

$k > 2$ można ulepszyć twierdzenie dotyczące hierarchii czasu: cstheory.stackexchange.com/questions/5297/…

— Michael Wehar

4

O twoje drugie pytanie. Nie, nie oznaczałoby to $P \neq NP$ . Twierdzenia dotyczące hierarchii przydają się przede wszystkim do określenia ilości pojedynczego zasobu wymaganego przez bazę TM, aby można było rozwiązać dodatkowe problemy.

Na przykład wiemy, że . Niech , , , tak że i . $DTIME(n) \neq NTIME(n)$ $f(n) = n$ $g(n)$ $h(n)$ $f(n+1) = o(g(n))$ $f(n)log(f(n)) = o ( h(n) )$

Z twierdzeń hierarchicznych wynika, że i . Przy tych założeniach jest możliwy. $DTIME( f(n) ) \subsetneq DTIME( g(n) )$ $NTIME ( f(n) ) \subsetneq NTIME( h(n) )$ $NTIME( g(n) ) \subseteq DTIME( h(n) )$

Twierdzenia o hierarchii można wykorzystać do określenia relacji między zasobami, biorąc pod uwagę ich równość. Załóżmy na przykład, że . Wiemy, że , dla tak że , nie może być równy SPACJI , z powodu twierdzenia o hierarchii NTIME. $NTIME(2^{n}) = SPACE( n )$ $NTIME( g(n) )$ $g(n)$ $2^{n+1} = o(g(n))$ $SPACE(n)$

— chazisop
źródło

1

Nie rozumiem, dlaczego luka nie mogła oznaczać . Oczywiście nie jest to bezpośrednia implikacja luki, ale być może istnieje inna pośrednia implikacja, która implikuje.

P \neq N P

$P \neq NP$

— Marc Bury,

0

hierarchia thms dotyczy również kontinuum w czasie i przestrzeni (rozpatrywanych osobno) i wydaje się możliwe, że kontinuum nie jest bardziej „ziarniste” niż wynika z twierdzeń, tzn. mogą być najlepszą możliwą „ziarnistością”.

twoje drugie pytanie wydaje się niejasne lub może nie jest dobrze zdefiniowane, chyba że możesz lepiej zdefiniować, co rozumiesz przez „lukę”. wszystkie rozstrzygalne problemy można rozwiązać gdzieś w obu hierarchiach. trudność polega na określeniu wzajemnych powiązań. jedna z rzadkich „luk” lub podziałów w obecnej teorii została rzeczywiście udowodniona w czasie deterministycznym w porównaniu z czasem niedeterministycznym, tak że [1]. zobacz także [2], aby uzyskać podobne pytanie i „najnowsze” osiągnięcia $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$

[1] PPST1983 http://dl.acm.org/citation.cfm?id=1382850

[2] NTIME (n ^ k) ≠ DTIME (n ^ k)?

— vzn
źródło