Inter-universal geometry とABC 予想57  

[過去ﾛｸﾞ] Inter-universal geometry とABC 予想57   (1002ﾚｽ)
上下前次1-新
通常表示 512ﾊﾞｲﾄ分割ﾚｽ栞
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

841: １３２人目の素数さん [sage] 2025/06/11(水) 08:25:17.56

>>839

計算量理論の二面性を示す主要文献を、正確な書誌情報と URL（スキームなし）および対応箇所の英語引用とともに示します。
1. 形式科学としての基盤
• Stephen A. Cook. The Complexity of Theorem-Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, May 1971, pp. 151–158. URL:
www.cs.toronto.edu/~sacook/homepage/1971.pdf
“Theorem 1. If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}.”
• Richard M. Karp. Reducibility among Combinatorial Problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, New York & London, 1972, pp. 85–103. URL:
link.springer.com/article/10.1007/978-1-4684-2001-2_9
“We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.”
2. 物理科学としての応用
• Scott Aaronson. NP-complete Problems and Physical Reality. SIGACT News 36(1), March 2005, pp. 30–52. URL:
www.scottaaronson.com/papers/npcomplete.pdf
“Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament–Hogarth spacetimes, quantum gravity, closed timelike curves, and ‘anthropic computing.’ The section on soap bubbles even includes some ‘experimental’ results.”
• Richard P. Feynman. Simulating Physics with Computers. International Journal of Theoretical Physics 21(6/7), June 1982, pp. 467–488. URL:
s2.smu.edu/~mitch/class/5395/papers/feynman-quantum-1981.pdf
“On the program it says this is a keynote speech—and I don’t know what a keynote speech is. I do not intend in any way to suggest what should be in this meeting as a keynote of the subjects or anything like that.”
“Simulation requirements: Exact – ‘The computer will do exactly the same as nature.’”

⸻

まとめ
これら四つの一次資料は、計算量理論が
• 数学的形式科学として「多項式時間還元」や「NP完全性」を厳密に定義し（Cook, Karp）、
• 物理科学として「現実世界の物理プロセス」を計算モデルに取り込み得ること（Aaronson, Feynman）を示しています。
両者を統合することで、計算資源の本質を探求する学際的領域としての計算量理論の全体像が得られます。

http://rio2016.5ch.net/test/read.cgi/math/1723187304/841

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.026s