Mengurangi kompleksitas dengan paralelisme

Apakah mungkin (slash dapat Anda berikan contoh) untuk mengurangi kompleksitas komputasi dari suatu masalah dengan menggunakan algoritma paralel yang tidak memerlukan sejumlah prosesor relatif terhadap ukuran input?

Jika yang Anda maksud adalah prosesor O (1), maka tidak ada, kompleksitas komputasi tidak dapat dikurangi.

Cukup sejajarkan pekerjaan yang dilakukan oleh masing-masing prosesor dan lakukan pada satu saja. Jika Anda khawatir tentang sinkronisasi, maka satu prosesor dapat dengan mudah meniru itu.

Ada bidang muncul dari algoritma paralel tdk halus, di mana waktu berjalan (dan konsumsi sumber daya komputasi lainnya) dianggap sebagai fungsi dari parameter independen n (ukuran input) dan p (jumlah prosesor), sering di bawah asumsi yang alami n >> p .

Titik awal yang baik adalah ke google untuk "paralelisme massal-sinkron".

Anda mungkin tertarik dengan makalah ini:

Kinerja Superlinear Dalam Komputasi Paralel Real-Time oleh Selim Akl.

$n$$n$

$p$$p$ adalah konstanta) prosesor.

$O(f(n)/p) \rightarrow O((1/p)f(n)) \rightarrow O(cf(n)) \rightarrow O(f(n))$$c=1/p$ .

$T$$T/p + SomeMoreTime$

Tapi NO kompleksitas berubah.

"Anda tidak dapat menghitungnya dengan 1 prosesor, tetapi dapat menghitung dengan 2."

Ini tidak mungkin, dengan asumsi bahwa kedua prosesor adalah TM atau model yang kurang kuat. Dari wikipedia, untuk mesin multi-tape:

Model ini secara intuitif tampak jauh lebih kuat daripada model pita tunggal, tetapi mesin multi-pita apa pun, tidak peduli seberapa besar k, dapat disimulasikan oleh mesin pita tunggal dengan hanya menggunakan waktu komputasi yang lebih kuadratik (Papadimitriou 1994, Thrm 2.1)

Juga untuk mesin multi-head, dari "Simulasi waktu linear mesin turing multihead dengan head - To-head jumps" oleh Walter J. Savitch dan Paul MB Vitányi:

Hasil utama dari makalah ini menunjukkan bahwa, mengingat mesin Turing dengan beberapa kepala baca-tulis per kaset dan yang memiliki operasi satu gerakan shift "menggeser kepala yang diberikan ke posisi beberapa kepala lain yang diberikan", seseorang dapat secara efektif membangun sebuah mesin Turing multitape dengan head baca-tulis tunggal yang mensimulasikannya dalam waktu linier; yaitu jika mesin asli beroperasi dalam waktu T (n), maka mesin simulasi akan beroperasi dalam waktu cT (n), untuk beberapa konstanta c.

Mungkin "paralel atau" (diberikan dua fungsi mengembalikan boolean, katakan apakah salah satu dari mereka mengembalikan true, mengingat bahwa salah satu dari mereka, tetapi tidak keduanya, mungkin gagal untuk mengakhiri) mungkin apa yang Anda bicarakan: Anda tidak dapat menghitung dengan 1 prosesor, tetapi dapat menghitung dengan 2.

Namun, ini sangat tergantung pada model komputasi yang akan Anda gunakan, apakah Anda diberikan proses sebagai kotak hitam atau sebagai deskripsi mereka yang dapat Anda interpretasikan sendiri, dll.