Existe um problema de computação que está no tempo quase polinomial, mas que talvez não esteja no

O tempo quase polinomial, ou QP, é uma classe de complexidade na máquina de Turing determinística. Aqui está a definição precisa: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

Enquanto βP é uma classe de complexidade de não determinismo limitado. Aqui está a definição precisa: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

É fácil ver que qualquer máquina de βP pode ser simulada por uma máquina de QP, ou seja, βP QP. $\subseteq$

Mas temos um exemplo, um problema que está no QP, mas não no βP, mesmo que não tenhamos uma prova precisa de que o problema não está no βP?

cc.complexity-theory complexity-classes Arthur Kexu-Wang
fonte

Seja f a função number_of_states_ e considere o problema

$\hspace{2.36 in}$ "M pára no máximo (f (M))

^{\log (f (M))}

$^{\hspace{.02 in}\log(\hspace{.04 in}f(M))}$

Respostas:

$QP-\beta P$ $\beta P$ $QP$ $NP$

$\bullet$ $\beta P\subseteq NP$

$\bullet$ $QP\subseteq NP$ $P\neq NP$ $P\neq NP$

$NP$ $\beta P\neq QP$

Andras Farago
fonte

β P

$\beta P$

Q P \subseteq N P

$QP\subseteq NP$

P \neq N P

$P\neq NP$

N P \subseteq Q P

$NP \subseteq QP$

N P \subset Q P

$NP \subset QP$

P v s N P

$P vs NP$

$\beta P$

Veja este post relacionado .

Este post da CS Theory de @Salamon indica que nem sabemos se a IG pode ser decidida com um não-determinismo de raiz quadrada e muito menos com um não-determinismo polilogarítmico.

Mohammad Al-Turkistany
fonte

No entanto, eu acho que muitas pessoas conjectura de que GI está em P.

Thomas

@Thomas Babai, em seu trabalho, indicou que ele é contra essa conjectura.

Mohammad Al-Turkistany

β P

$\beta P$

β P

$\beta P$

@JoshuaGrochow Sim, o comentário é mais específico (apontando a parte específica sobre o diploma). Mas a resposta apenas faz referência à pergunta sobre MO como o que considero uma forte dica para a alegação de que não há provas - o que me parece circular.

Clement C.