問答題

【簡答題】RAM程序、RASP程序與Turing機相互之間的時間復(fù)雜度關(guān)系是怎樣的（考慮兩種耗費標準）？

答案：任何一個RAM程序，都可由一個RASP程序來模擬實現(xiàn)，且時間復(fù)雜性數(shù)量級相同（不論哪一種耗費標準）。即如果RAM程序的時...

你可能感興趣的試題

【簡答題】Church-Turing Thesis的內(nèi)容是什么？它有什么意義？

答案：任何合理的計算模型都是相互等價的（計算范圍相同）。
合理：單位時間內(nèi)可以完成的工作量，有一個多項式的上限。不合...

【簡答題】Alan Turing是怎樣對人類計算過程進行概括的？

答案： Turing根據(jù)這個過程構(gòu)造出了一個計算模型，稱之為Turing機。
這個計算模型有一條帶子（帶子相當(dāng)于一張紙...