Por que o NP está EXPTIME?

Existe uma maneira fácil de entender por que o NP está em EXPTIME? Parece-me a priori concebível que poderia haver um problema que requer tempo superexponencial para ser resolvido, mas cuja solução poderia ser verificada em tempo polinomial.

complexity-theory complexity-classes tparker
fonte

De fato, NP

PSPACE.

\subseteq

$\subseteq$

Bem-vindo à Ciência da Computação! O que você tentou? Onde você ficou preso? Não queremos apenas fazer o seu trabalho (em casa) para você; queremos que você obtenha entendimento. No entanto, como não sabemos qual é o seu problema subjacente, não podemos começar a ajudar. Veja aqui uma discussão relevante. Se você não souber como melhorar sua pergunta, por que não perguntar no Computer Science Chat ? Você também pode conferir nossas perguntas de referência .

Raphael

Respostas:

Qualquer problema no NP está em EXPTIME porque você pode usar o tempo exponencial para tentar todos os certificados possíveis ou enumerar todos os caminhos de computação possíveis de uma máquina não determinística.

$L$ $R$

$p$ $(x,y)\in R$ $|y|\leq p(|x|)$
$x\#y$ $|x\#y|$ $(x,y)\in R$
$L = \{x\mid (x,y)\in R\}$

$x\in L$ $|\Sigma|^{p(n)}$ $y$ $(x,y)\in R$ $2^{O(p(n))}$ $L\in\,$ EXPTIME .

$L$ $M$ $p(n)$ $p$ $n$ $M$ $p(|x|)$ $x\in L$ $M$ $k$ $M$ $k$ $k^{p(|x|)} = 2^{O(p(|x|))}$ $x$

David Richerby
fonte

x

$x$

y

$y$

O (k^{| x |})

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

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

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

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

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