Isomorfismo de Berman-Hartman para NP ?

10

Usando o modelo real-RAM / BSS, temos a classe NP , (onde um BSS é o modelo Blum-Shub-Smale de um computador com operações sobre reais). Temos NP problemas completos. Então, a questão é: existe um análogo da conjectura de Berman Hartman para a classe NP ? Obviamente, a questão colocada aqui depende do modelo - em outras palavras, como a definição de NP usa o modelo BSS, todos os problemas completos de NP têm o mesma estrutura usando o modelo BSS (isso aproxima a conjectura de Berman-Hartmanis para NP sobre reais)?RRRRR

user3483902
fonte

Respostas:

8

Dependendo de qual versão do você usa, sim ou é aberta. Quando se considera máquinas BSS que usam apenas adição e subação, e apenas ramificam a igualdade, a resposta é sim. Se alguém incluir ramificações em < , acredito que ainda esteja aberto, e o mesmo se permitir multiplicações. Para detalhes, consulte Cucker, Koiran e Matamala "Complexidade e dimensão", Inform. Proc. Lett. 1997NPR<

Joshua Grochow
fonte
11
A sensibilidade às operações é crucial para a máquina, por exemplo, se permitirmos apenas a adição e multiplicação da máquina, os conjuntos reconhecidos pela máquina BSS mudam.
user3483902