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 $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$ ?

— Kaveh
źródło

Nie jestem pewien, ale myślę, że z podobnych argumentów użytych w poprzednim pytaniu, które mamy

T M S A T = {< a, x, 1^{n}, 1^{t} >: \exists u \in {0, 1}^{n} s . t . M_{a} o u t p u t s 1 o n i n p u t < x, u > w i t h i n t s t e p s}

$\mathsf{TMSAT}=\{<a,x,1^n,1^t>:\exists u\in \{0,1\}^n\: s.t. \: M_a\: outputs\:1\: on\: input\: <x,u> \: within \: t \: steps \}$ nie jest w

D T I M E (n^{2} / \lg n)

$\mathsf{DTIME}(n^2/\lg{n})$ . Tak właściwie

T M S A T

$\mathsf{TMSAT}$ nie jest w

D T I M E (n)

$\mathsf{DTIME}(n)$ , ponieważ

N T I M E (n) \neq D T I M E (n)

$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$ , ale nie znam lepszych dolnych granic.

— Erfan Khaniki

@Erfan, mój argument nie pokazuje, że tak nie jest, ani nie pokazuje, że jest mało prawdopodobne, po prostu pokazuje, że udowodnienie, że jest nieznane i trudne

ω (n \lg n)^{2}

$\omega(n\lg n)^2$ .

— Kaveh

Tak masz rację. W rzeczywistości ten argument pokazuje, że trudno to udowodnić

D T I M E (n^{2}) \subseteq N T I M E (n)

$\mathsf{DTIME}(n^2)\subseteq \mathsf{NTIME}(n)$ .

— Erfan Khaniki

Zauważ, że nawet wynik zgodny z $\mathsf{DTime}(\tilde{O}(n^2)) \subseteq \mathsf{NTime}(n^{2-\epsilon})$ to łamią NSETH w jednowymiarowej testów tożsamości wielomianu (jak zdefiniowany w punkcie 3.2) może być rozwiązany $\tilde{O}(n^2)$ czas deterministycznie, ale wydaje się, że nie ma oczywistego sposobu na użycie niedeterminizmu w celu udowodnienia tożsamości.

— Joe Bebel
źródło