复杂性与真实计算
Complexity and real computation
Lenore Blum · 初版 1998 年
2人推荐
2位读者提及
4次提及
经典计算理论源自 Goedel、Turing、Church 和 Kleene 的开创性工作，一直是理论计算机科学极为成功的基石框架。然而本书的核心论点指出，对于大多数算法都基于实数的现代科学计算而言，这一框架所提供的基础并不充分。本书旨在建立一套形式化的计算理论，将经典理论的主要脉络融汇其中，并使其更直接地适用于数学、数值分析及科学计算中的各类问题。沿着这
Hacker News 上怎么说
正在加载完整评论……
去了解一下 Lenore Blum 的成果吧。她写过一本书叫《Complexity and Real Computation》。
Look into work of Lenora Blum. She wrote a book "Complexity and Real computation".
扩展阿兰·图灵-丘奇论题（extended Church-Turing thesis）指出，模拟计算机可以在图灵机上被模拟。确实可以，但效率不高。去看看 Lenore Blum 的工作吧。她写了一本书叫《Complexity and Real Computation》。
The extended Turing-Church thesis states that an analog computer can be simulated on a Turing machine. It can but not efficiently. Look into the work of Lenora Blum. She wrote a book "Complexity and Real computation".
……它并不适用于图灵机模型，而图灵机正是大多数人听到 P vs NP 时脑海里浮现的东西。90 年代有一本关于 BSS 模型的极好、而且在数学上很易读的书：由 Lenore Blum、Felipe Cucker、Michael Shub 和 Steve Smale 合著的《Complexity and Real Computation》。我本来以为这会开辟出一个庞大的领域，但不知道后来有没有什么大动静。另见：https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...
…it doesn't apply to the Turing machine model which is what most people think of when they hear of P vs NP. There is a wonderful and mathematically accessible book from the 1990s about the BSS model: Complexity and Real Computation, by Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. I thought it was going to open up into a big field, but I don't know if much happened with it. See also: https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...
……尤其是考虑到目前连续变量系统的大多用途是用来编码离散量子比特。目前用途也许是这样吧。> 有没有关于连续变量模型的复杂度理论（Complexity Theory）研究发表？《Complexity and Real Computation》。> 而且光子系统并不能神奇地解决噪声问题。噪声随着系统规模呈快速非线性增长，因此切换架构所换来的“常数级因子”噪声抑制……
…Especially given that most uses of the continuous variable systems is to encode discrete qubits Current uses, maybe. > Is there any Complexity Theory work published about continuous variable models? "Complexity and Real Computation". > And photonic systems do not magically fix the noise issue. Noise grows in a fast non-linear fashion with the size of the system, so the "constant factor" noise suppression you gain from switching…