Mesin Akses Acak dengan hanya penambahan, multiplikasi, persamaan

Literatur cukup jelas bahwa RAM unit-biaya dengan perkalian primitif tidak masuk akal, dalam hal itu mereka

tidak dapat disimulasikan oleh mesin Turing dalam waktu polinomial
dapat menyelesaikan masalah PSPACE-complete dalam waktu polinomial

Namun, semua referensi yang dapat saya temukan pada topik ini (Simon 1974, Schonhage 1979) juga melibatkan operasi boolean, pembagian integer, dll.

Apakah ada hasil untuk "kewajaran" dari RAM yang hanya memiliki penambahan, perkalian, dan kesetaraan? Dengan kata lain, yang tidak memiliki operasi boolean, divisi integer terpotong, pengurangan terpotong, dll?

Orang akan berpikir bahwa RAM semacam itu masih "tidak masuk akal." Bendera merah utama adalah bahwa mereka memungkinkan generasi bilangan bulat besar secara eksponensial dalam waktu linier, dan karena efek konvolusi dari perkalian, ini bisa menjadi sangat kompleks. Namun, saya tidak dapat benar-benar menemukan hasil yang menunjukkan bahwa ini memungkinkan untuk segala jenis hasil "tidak masuk akal" (percepatan eksponensial dari mesin Turing, hubungan tidak masuk akal dengan PSPACE, dll).

Apakah literatur memiliki hasil pada topik ini?

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

Yuval Filmus memiliki catatan singkat yang merangkum bagaimana memecahkan masalah dalam NP (dan saya pikir ada masalah di PSPACE?) Dalam waktu polinomial, menggunakan RAM unit-cost. Mungkin dia akan memposting tautan untuk itu dan Anda dapat meninjau metode di sana untuk melihat apakah mereka dapat digeneralisasi untuk menghilangkan kebutuhan pembagian.

Dapatkah Anda memikirkan cara untuk menghitung jumlah

, di mana

adalah konstanta kecil, dalam model Anda, menggunakan waktu polinomial di

? Dengan kata lain, kami ingin menghitung

. Ini dapat dilakukan dalam waktu polinomial dalam

dan

\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$ jika kita mengizinkan perpecahan, tetapi dapatkah itu dilakukan tanpa perpecahan? Jika bisa, saya menduga hasil yang serupa juga akan berlaku untuk model Anda.

Apakah Anda tahu di mana catatan ini? Saya telah melihat literatur tentang RAM unit-biaya menjadi sangat kuat ketika operasi boolean diizinkan, dan pemotongan divisi (atau shift), dengan operasi dan pemotongan boolean pada dasarnya mengubah semuanya menjadi perangkat paralel besar. Tetapi, harus ada beberapa hasil di suatu tempat yang menunjukkan bahwa bahkan hanya perkalian unit-biaya adalah "tidak masuk akal" tanpa hal-hal lain, karena seperti yang disebutkan, Anda dapat dengan cepat menghitung angka dengan lebih banyak angka daripada yang terkandung dalam alam semesta yang dapat diamati. Tetapi, saya tidak dapat menemukan bukti tentang ini.

Mike Battaglia

@ WD Catatan saya menunjukkan bagaimana menyelesaikan semua masalah di PSPACE dalam waktu polinomial. Sayangnya, Anda perlu menggunakan operator bitwise (bitwise AND dan OR; keduanya setara). Pada saat itu saya secara singkat memikirkan pertanyaan yang Anda tanyakan, tetapi tidak ada kesimpulan. Anda dapat menemukan semua ini di sini , meskipun sepertinya Anda sudah menyadarinya.

Yuval Filmus

P \in PSPACE

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

Mesin Akses Acak dengan hanya penambahan, multiplikasi, persamaan

Jawaban: