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

9

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.

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?

Arthur Kexu-Wang
fonte
4
Seja f a função number_of_states_ e considere o problema "M pára no máximo (f (M))log(f(M))

Respostas:

4

QPβPβPQPNP

βPNP

QPNPPNPPNP

NPβPQP

Andras Farago
fonte
2
βP
QPNPPNPNPQPNPQPPvsNP
3

βP

β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
11
No entanto, eu acho que muitas pessoas conjectura de que GI está em P.
Thomas
11
@Thomas Babai, em seu trabalho, indicou que ele é contra essa conjectura.
Mohammad Al-Turkistany
2
βP
11
βP
11
@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.