Máquinas de acesso aleatório com apenas adição, multiplicação, igualdade

A literatura é bastante clara que RAMs de custo unitário com multiplicação primitiva são irracionais, pois

não pode ser simulado por máquinas de Turing em tempo polinomial
pode resolver problemas completos do PSPACE em tempo polinomial

No entanto, todas as referências que posso encontrar sobre esse tópico (Simon 1974, Schonhage 1979) também envolvem operações booleanas, divisão inteira etc.

Existem resultados para a "razoabilidade" das RAMs que possuem apenas adição, multiplicação e igualdade? Em outras palavras, quais não possuem operações booleanas, divisão inteira truncada, subtração truncada, etc?

Alguém poderia pensar que essas RAMs ainda são bastante "irracionais". A principal bandeira vermelha é que eles permitem a geração de números inteiros exponencialmente grandes em tempo linear e, devido aos efeitos de convolução da multiplicação, isso pode se tornar particularmente complexo. No entanto, não consigo encontrar nenhum resultado mostrando que isso permita qualquer tipo de resultado "irracional" (aceleração exponencial da máquina de Turing, relacionamento irracional com o PSPACE, etc.).

A literatura tem algum resultado sobre esse tópico?

complexity-theory reference-request computation-models history Mike Battaglia
fonte

Yuval Filmus tem uma breve nota resumindo como resolver qualquer problema no NP (e acho que existe algum problema no PSPACE?) Em tempo polinomial, usando RAMs de custo unitário. Talvez ele publique um link para isso e você possa revisar os métodos lá para ver se eles podem ser generalizados para eliminar a necessidade de divisão.

Você pode pensar em uma maneira de calcular o número

, onde

é uma pequena constante, no seu modelo, usando o polinômio de tempo em

? Em outras palavras, queremos calcular

. Isso pode ser feito em polinomial vez em

\sum_{i = 0}^{2^{n} - 1} 2^{c i}

$\sum_{i=0}^{2^n-1} 2^{ci}$

c

$c$

n, c

$n,c$

(2^{c 2^{n}} - 1) / (2^{c} - 1)

$(2^{c 2^n}-1)/(2^c-1)$

n

$n$

c

$c$ se permitirmos a divisão, mas isso pode ser feito sem divisão? Se possível, suspeito que resultados semelhantes também se apliquem ao seu modelo.

Você sabe onde está esta nota? Eu já vi literatura sobre RAMs de custo unitário ser excessivamente poderosa quando operações booleanas são permitidas e divisão (ou turno) truncada, com as operações e truncamentos booleanos basicamente transformando tudo em um enorme dispositivo paralelo. Mas deve haver algum resultado em algum lugar mostrando que mesmo apenas a multiplicação do custo unitário é "irracional" sem as outras coisas, porque, como mencionado, você pode calcular rapidamente números com mais dígitos do que o contido no universo observável. Mas não consigo encontrar uma prova disso.

Mike Battaglia

@DW Minha observação mostra como resolver todos os problemas no PSPACE em tempo polinomial. Infelizmente, você precisa usar operadores bit a bit (AND e OR bit a bit; os dois são equivalentes). Naquele momento, pensei brevemente na própria pergunta que você está fazendo, mas não cheguei a nenhuma conclusão. Você pode encontrar tudo isso aqui , embora pareça que você já está ciente disso.

Yuval Filmus

P \in PSPACE

$\text{P} \in \text{PSPACE}$

Máquinas de acesso aleatório com apenas adição, multiplicação, igualdade

Respostas: