Maszyny o dostępie swobodnym z tylko dodawaniem, mnożeniem, równością

Literatura jest dość jasna, że jednostronne pamięci RAM z pierwotnym mnożeniem są nieuzasadnione, ponieważ są

nie mogą być symulowane przez maszyny Turinga w czasie wielomianowym
potrafi rozwiązać problemy związane z PSPACE w czasie wielomianowym

Jednak wszystkie odniesienia, które mogę znaleźć na ten temat (Simon 1974, Schonhage 1979) obejmują również operacje boolowskie, dzielenie liczb całkowitych itp.

Czy istnieją jakieś wyniki dotyczące „racjonalności” pamięci RAM, które mają tylko dodawanie, mnożenie i równość? Innymi słowy, które nie mają operacji boolowskich, obciętego podziału na liczby całkowite, obciętego odejmowania itp.?

Można by pomyśleć, że takie pamięci RAM są nadal „nieuzasadnione”. Główną czerwoną flagą jest to, że umożliwiają generowanie wykładniczo dużych liczb całkowitych w czasie liniowym, a ze względu na splotowe efekty mnożenia może to być szczególnie złożone. Jednak nie mogę znaleźć żadnych wyników wskazujących, że pozwala to na jakiekolwiek „nieuzasadnione” wyniki (wykładnicze przyspieszenie maszyny Turinga, nieuzasadnione powiązanie z PSPACE itp.).

Czy literatura ma jakieś wyniki na ten temat?

complexity-theory reference-request computation-models history Mike Battaglia
źródło

Yuval Filmus ma krótką notatkę podsumowującą, jak rozwiązać dowolny problem w NP (i myślę, że jakikolwiek problem w PSPACE?) W czasie wielomianowym, używając RAM-ów jednostkowych. Być może opublikuje link do tego i możesz przejrzeć tam metody, aby sprawdzić, czy można je uogólnić, aby wyeliminować potrzebę podziału.

Czy możesz pomyśleć o sposobie obliczenia liczby , gdzie jest małą stałą w twoim modelu, używając wielomianu czasowego w ? Innymi słowy, chcemy obliczyć . Można to zrobić w czasie wielomianu w i jeśli pozwolimy podział, ale można to zrobić bez podziału? Jeśli to możliwe, podejrzewam, że podobne wyniki będą miały zastosowanie również do twojego modelu.

\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$

Czy wiesz, gdzie jest ta notatka? Widziałem literaturę na temat RAM o jednostkowych kosztach, które są niewiarygodnie potężne, gdy dozwolone są operacje boolowskie, oraz skrócony podział (lub przesunięcie), przy czym operacje boolowskie i skróty zasadniczo zmieniają całość w ogromne równoległe urządzenie. Ale gdzieś powinien być jakiś wynik pokazujący, że nawet samo zwielokrotnienie kosztu jednostkowego jest „nieuzasadnione” bez innych rzeczy, ponieważ, jak wspomniano, możesz szybko obliczyć liczby z większą liczbą cyfr niż jest to możliwe w obserwowalnym wszechświecie. Ale nie mogę znaleźć na to dowodu.

Mike Battaglia,

@DW Moja notatka pokazuje, jak rozwiązać wszystkie problemy w PSPACE w czasie wielomianowym. Niestety musisz użyć operatorów bitowych (bitowe AND i OR; oba są równoważne). Wtedy krótko myślałem o samym pytaniu, ale nie doszedłem do wniosku. Możesz to wszystko znaleźć tutaj , choć wydaje się, że już jesteś tego świadomy.

Yuval Filmus

Dzięki - rzeczywiście to widziałem. Myślę, zastanawiam się, jak to może nie być tak, że nie ma przyspieszenie tylko z mnożenia? Możesz ciągle zwiększać kwadrat do liczb, aby uzyskać wykładniczo duże, bardzo złożone wzory, które wydają się szalone dla maszyny Turinga wytwarzającej w czasie wielomianowym. Czy nie powinien istnieć jakikolwiek argument dotyczący wzrostu, ponieważ wydaje się, że używamy przestrzeni wykładniczej w czasie liniowym (naruszając )? Te problemy nie dotyczą dodawania kosztu jednostkowego, tylko pomnożenie.

P \in PSPACE

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

Mike Battaglia,

Maszyny o dostępie swobodnym z tylko dodawaniem, mnożeniem, równością

Odpowiedzi: