Jak szybko niedeterministyczny algorytm dla problemu pełnego EXPTIME musiałby sugerować

Jak szybko niedeterministyczny algorytm dla problemu pełnego EXPTIME musiałby sugerować ? Algorytm niedeterministyczny czasu wielomianowego natychmiast implikowałby to, ponieważ ale nikt nie wierzy, że . Jeśli zrobiłem algebrę w prawo (patrz poniżej), twierdzenie o hierarchii czasu nadal dawałoby implikację dla czasów uruchamiania dla dowolnego wielobiegunowego , ale dla wszystko, co wiem, to całkowite problemy z wydajnymi redukcjami, które pozwalają wolniejszym algorytmom dawać wynik. Czy występują problemy z pełnymi wyjątkami, gdy wiemy coś w rodzaju lub $P \neq NP$ $P \neq EXPTIME$ $NP = EXPTIME$ $P \neq NP$ $O(2^n/f(n))$ $f(\cdot)$ $2^n/n$ $2^n/n^2$ z niedeterminizmem wystarczy?

Wyjaśnienie „algebry”: implikuje przez argument dopełniający, więc niedeterministyczny algorytm dla problemu pełnego EXPTIME byłby również jednym dla problemu pełnego NEXPTIME. W przypadku wielobiegunowego byłoby to sprzeczne z niedeterministycznym twierdzeniem o hierarchii czasu, ponieważ moglibyśmy zmniejszyć używając NTIME . $P = NP$ $EXPTIME=NEXPTIME$ $2^n/f(n)$ $f(\cdot)$ $L \in$ $(2^n)$

cc.complexity-theory Anonimowy
źródło

Myślę, że tak naprawdę potrzebujesz czasu działania aby uzyskać sprzeczność z twierdzeniem o hierarchii czasu. Wydaje mi się też, że to mało prawdopodobne.

2^{n^{o (1)}}

$2^{n^{o(1)}}$

Sasho Nikolov

Wystarczy powtórzyć pytanie: jaki jest największy

f

$f$ gdzie ExpTime

\subseteq

$\subseteq$ NTime

(f (n))

$(f(n))$ oznacza NP

⊈

$\not\subseteq$ P?

Kaveh

ps: jeśli zarejestrujesz konto, możesz łatwiej edytować swoje pytanie.

Kaveh

Uważam, że Sasho ma rację, jeśli

E X P T I M E = N E X P T I M E

$EXPTIME=NEXPTIME$ taki, że

L

$L$ jest

E X P T I M E

$EXPTIME$ a

L^{'}

$L'$ jest

N E X P T I M E

$NEXPTIME$ a

L^{'}

$L'$ jest redukowalne do

L

$L$ w czasie

O (n^{k})

$O(n^k)$ , to nadal możliwe jest, że

L \in N T I M E (2^{\sqrt[k]{n}})

$L \in NTIME(2^{\sqrt[k]{n}})$ bez żadnych sprzeczności, ponieważ wystąpienie

L

$L$ może być

O (n^{k})

$O(n^k)$ większe niż

L^{'}

$L'$ .

Joe Bebel,

Odpowiedzi:

Myślę, że łatwiej to odwrócić.

Jeśli , to dla jakiegoś stałego i dowolnego . Ponieważ nie zawiera , oznacza to, że nie możemy rozwiązać, powiedz wszystkie problemy w w dla niektórych . algorytm niedeterministyczny dla kompletnego problemu dla przy quasi-liniowych redukcjach wystarczyłby do udowodnienia $\mathsf{P}=\mathsf{NP}$ $\mathsf{NTIME}(T(n)) \subset \mathsf{DTIME} ((T(n))^c)$ $c$ $T(n) > n$ $\mathsf{DTIME} ((T(n)^c)$ $\mathsf{DTIME}(T(n)^{c}\log T(n)) \subset \mathsf{DTIME}(T(n)^{c+1})$ $\mathsf{DTIME}(2^n)$ $\mathsf{NTIME} (2^{\epsilon n})$ $\epsilon$ $2^{o(n)}$ $\mathsf{DTIME} (2^n)$ $\mathsf{P} \neq \mathsf{NP}$ .

Russell Impagliazzo
źródło

Dziękujemy za czasu na krótsze wyjaśnienie, dlaczego implikuje .

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

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

P \neq N P

$P \neq NP$

Michael Wehar,

I dzięki za wskazanie, że można zastosować twierdzenie o deterministycznej lub niedeterministycznej hierarchii czasu. :)

Michael Wehar

Prosta odpowiedź: dla każdego - problem istnieje jakiś stały taki że gdybyśmy mogli rozwiązać problem w , to . $EXPTIME$ $hard$ $c$ $NTIME(2^{o(n^{\frac{1}{c}})})$ $P \neq NP$

Uwaga: Stała pochodzi od powiększeń wielkości instancji wynikających z redukcji. $c$

Uzasadnienie: Niech oznaczają - problem. Oznacza to, że każdy problem w jest wielomian czas sprowadzić do . W rzeczywistości możemy pokazać więcej. $X$ $EXPTIME$ $hard$ $EXPTIME$ $X$

Problem akceptacja czasu ograniczone deterministycznych maszyny Turinga w i dlatego jest wielomianem czas zredukować do . $2^n$ $DTIME(n \cdot 2^n) \subseteq EXPTIME$ $X$

Dlatego musi istnieć pewna stała stała tak aby każdy problem w był czasem wielomianowym redukowalnym do gdzie powiększenie wielkości instancji wynosi . Oznacza to, że przykłady wielkości n są ograniczone do przypadków rozmiaru o . $c$ $DTIME(2^n)$ $X$ $O(n^c)$ $O(n^c)$ $X$

Teraz, jeśli mielibyśmy , to . Implikuje to jednak (szczegóły poniżej). $X \in NTIME(2^{o(n^{\frac{1}{c}})})$ $DTIME(2^n) \subseteq NTIME(2^{o(n)})$ $P \neq NP$

Dodatkowe szczegóły: Można pokazać, że . $P=NP$ $\Leftrightarrow$ $\exists c^{\prime}$ $\forall k$ $NTIME(n^k) \subseteq DTIME(n^{c^{\prime}k})$

Innymi słowy, jeśli możesz rozwiązać - w czasie wielomianowym, istnieje jednolity sposób przyspieszenia dowolnego problemu w . $NP$ $complete$ $NP$

Załóżmy teraz, że . Przez poprzednie (z = 1) otrzymujemy stałą taką, że $P=NP$ $k$ $c^{\prime}$

N T I M E (n) \subseteq D T I M E (n^{c^{'}}) .

$NTIME(n) \subseteq DTIME(n^{c^{\prime}}).$

Następnie możemy użyć dopełnienia, aby zwiększyć skalę tego włączenia i uzyskać

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

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

Następnie, według twierdzenia o deterministycznej hierarchii czasu, mamy dla dowolnego .

N T I M E (2^{n}) \subseteq D T I M E (2^{c^{'} n}) ⊊ D T I M E (2^{(c^{'} + ϵ) n})

$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}) \subsetneq DTIME(2^{(c^{\prime}+\epsilon)n})$

ϵ > 0

$\epsilon > 0$

Dlatego nie mogliśmy mieć $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{n}).$

Co więcej, nie mogliśmy mieć ponieważ przez wypełnienie otrzymalibyśmy . $DTIME(2^{n}) \subseteq NTIME(2^{o(n)})$ $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{o(n)})$

Dalsze pytanie: Czy ktoś ma jakieś proste przykłady - problemy, w których możemy łatwo określić stałą wysadzenia rozmiaru instancji ? $EXPTIME$ $complete$ $c$

Michael Wehar
źródło

Problemem akceptacji jest sam , to znaczy język składający się z DTM które na wejściu akceptują w ciągu kroków, ponieważ każdy język ma część która akceptuje w czasie dla pewnego , więc właściwy wybór zmniejsza do . W szczególności stała ( ) wydaje się wtedy pokazywać, że przyspieszenie (to znaczy

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

$DTIME(2^n)$

E X P T I M E

$EXPTIME$

L = {⟨ T, x, 1^{m} ⟩}

$L = \{\langle T, x, 1^m \rangle\}$

T

$T$

x

$x$

2^{m}

$2^m$

L^{'} \in E X P T I M E

$L' \in EXPTIME$

T

$T$

x \in L^{'}

$x \in L'$

2^{O (| x |^{k})})

$2^{O(|x|^k)})$

k

$k$

m = O (| x |^{k})

$m = O(|x|^k)$

L^{'}

$L'$

L

$L$

c = 1

$c=1$

f (n)

$f(n)$ ) musi być wykładniczy, jeśli ma być wyświetlany , jeśli wybierzesz ten konkretny język z .

P \neq N P

$P \ne NP$

E X P T I M E

$EXPTIME$

Joe Bebel,

@JoeBebel Cześć Joe, dziękuję za komentarz. Myślę, że to cenne, że dodatkowo rozważyć ten problem . Tutaj możemy powiedzieć więcej niż tylko oznacza . W przypadku tego konkretnego sztucznego problemu możemy być w stanie powiedzieć coś jak dla dowolnego , implikuje dla wszystkich .

L

$L$

L \in N T I M E (2^{o (n)})

$L \in NTIME(2^{o(n)})$

P \neq N P

$P \neq NP$

L

$L$

k

$k$

L \in N T I M E (2^{\frac{n}{k}})

$L \in NTIME(2^{\frac{n}{k}})$

N T I M E (n) ⊈ D T I M E (n^{k - ϵ})

$NTIME(n) \nsubseteq DTIME(n^{k-\epsilon})$

ϵ > 0

$\epsilon > 0$

Michael Wehar