Qual a rapidez que um algoritmo não determinístico para um problema EXPTIME-completo teria de implicar

Qual a velocidade de um algoritmo não determinístico para um problema EXPTIME-completo para implicar ? Um algoritmo não determinístico de tempo polinomial implicaria isso imediatamente porque mas ninguém acredita que . Se eu fiz a álgebra corretamente (veja abaixo), o teorema da hierarquia de tempo ainda daria a implicação para os tempos de execução de para qualquer superpolinômio , mas para tudo o que sei são problemas completos com reduções eficientes que permitem que algoritmos mais lentos produzam o resultado. Existem problemas EXPTIME-complete em que sabemos algo como ou $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$ com não-determinismo é suficiente?

O esclarecimento da "álgebra": implica por um argumento de preenchimento; portanto, um algoritmo para um problema de EXPTIME-completo seria também um problema de NEXPTIME-completo. Para o superpolinômio isso contradiz o teorema da hierarquia de tempo não determinístico, pois podemos reduzir o uso de algum NTIME . $P = NP$ $EXPTIME=NEXPTIME$ $2^n/f(n)$ $f(\cdot)$ $L \in$ $(2^n)$

cc.complexity-theory Anônimo
fonte

Eu acho que você realmente precisa de tempo de execução

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

$2^{n^{o(1)}}$ para obter uma contradição a partir do teorema de hierarquia de tempo. Também acho que isso parece bastante improvável.

Sasho Nikolov

f

$f$

\subseteq

$\subseteq$

(f (n))

$(f(n))$

⊈

$\not\subseteq$

ps: se você registrar uma conta, poderá editar sua pergunta mais facilmente.

Kaveh

Acredito que Sasho está correto, se modo que seja -complete e seja -complete e seja redutível a no tempo , ainda é possível que sem qualquer contradição, porque a instância de pode ser maior que .

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

$EXPTIME=NEXPTIME$

L

$L$

E X P T I M E

$EXPTIME$

L^{'}

$L'$

N E X P T I M E

$NEXPTIME$

L^{'}

$L'$

L

$L$

O (n^{k})

$O(n^k)$

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

$L \in NTIME(2^{\sqrt[k]{n}})$

L

$L$

O (n^{k})

$O(n^k)$

L^{'}

$L'$

21715 Joe

Respostas:

Eu acho que é mais fácil mudar isso.

Se , para alguma constante , e qualquer . Como não contém , isto significa que não podemos resolver, digamos todos os problemas em em para alguns . um algoritmo tempo não determinístico para um problema completo para sob reduções quase lineares seria suficiente para provar $\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
fonte

Obrigado por dedicar um tempo para fornecer uma explicação mais breve de por que implica .

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

E, obrigado por apontar que o teorema da hierarquia de tempo determinístico ou não determinístico poderia ser usado. :)

Michael Wehar

Resposta simples: Para cada - problema existe alguma constante de tal forma que se poderia resolver o problema em $EXPTIME$ $hard$ $c$ , então. $NTIME(2^{o(n^{\frac{1}{c}})})$ $P \neq NP$

Nota: A constante é proveniente das ampliações do tamanho da instância que resultam das reduções. $c$

Justificação: Let denotam um - problema. Isso significa que todos os problemas é redutível em tempo polinomial para . De fato, podemos mostrar mais. $X$ $EXPTIME$ $hard$ $EXPTIME$ $X$

O problema aceitação por tempo limitado máquinas de Turing determinísticos é em e, portanto, é redutível tempo polinomial para . $2^n$ $DTIME(n \cdot 2^n) \subseteq EXPTIME$ $X$

Portanto, deve haver alguma constante fixa modo que todo problema em seja polinomial redutível a onde o tamanho da instância é . Ou seja, os casos de tamanho n são reduzidos para os casos de tamanho para . $c$ $DTIME(2^n)$ $X$ $O(n^c)$ $O(n^c)$ $X$

Agora, se tivéssemos , então. No entanto, isso implica(veja detalhes abaixo). $X \in NTIME(2^{o(n^{\frac{1}{c}})})$ $DTIME(2^n) \subseteq NTIME(2^{o(n)})$ $P \neq NP$

Detalhes adicionais: Pode-se mostrar que . $P=NP$ $\Leftrightarrow$ $\exists c^{\prime}$ $\forall k$ $NTIME(n^k) \subseteq DTIME(n^{c^{\prime}k})$

Em outras palavras, se você pode resolver um - problema em tempo polinomial, então há uma maneira uniforme de acelerar qualquer problema em . $NP$ $complete$ $NP$

Agora, vamos supor que . Pelo anterior (com = 1), obtemos uma constante tal que $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}}).$

Em seguida, podemos usar o preenchimento para aumentar essa inclusão e obter

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}).$

Em seguida, pelo teorema de hierarquia de tempo determinista, temos para qualquer .

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$

Portanto, não podemos ter $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{n}).$

Além disso, não poderíamos ter porque, preenchendo, obteríamos . $DTIME(2^{n}) \subseteq NTIME(2^{o(n)})$ $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{o(n)})$

Além disso Pergunta: Alguém tem alguma exemplos simples de - problemas onde podemos facilmente determinar o tamanho da instância blow-up constante ? $EXPTIME$ $complete$ $c$

Michael Wehar
fonte

O problema aceitação para

é por si só

-completo, isto é, a língua

consistindo de DTM

que na entrada

aceitar dentro de

etapas, porque cada língua

tem alguns

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$

que aceita

em vez

de alguns

, de modo que a escolha adequada de

reduz

. Em particular, a constante (

) parece mostrar que a aceleração (ou seja,

) deve ser exponencial para mostrar

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)$

P \neq N P

$P \ne NP$ , se você escolher esse idioma completo

E X P T I M E

$EXPTIME$

21715 Joe

@ JoeBebel Oi Joe, obrigado pelo comentário. Eu acho que é importante que você ainda considerado este problema

. Aqui, podemos dizer mais do que apenas

implica

. Para esse problema artificial específico

, podemos dizer algo como para qualquer

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$

implica

para todos

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 13/03/2015