計算量理論入門 - 時間と空間の制限 - 第3回
Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only! Grab it Learn about computational complexity theory in this Japanese lecture from the Research Institute for Mathematical Sciences at Kyoto University's 42nd Public Mathematics Course. Explore how computers extend human mathematical capabilities and problem-solving abilities, while examining the fundamental complexities that persist despite technological advances. Delve into key concepts including polynomial time, polynomial space, and complexity hierarchies through practical examples like string rewriting problems. Follow along as Associate Professor Akitoshi Kawamura breaks down how to measure computational difficulty across various mathematical objects, discusses important theoretical frameworks, and addresses applications and unsolved conjectures in the field. The lecture includes a comprehensive Q&A session and builds upon previous course material, serving as the third installment in a four-part series focused on understanding and quantifying complexity in computational theory.