(06-09 12:00) [강연회] An algebro-geometric approach to computational complexity | |||||
작성자 | 과사무실 | ||||
---|---|---|---|---|---|
조회수 | 674 | 등록일 | 2022.02.14 | ||
일시 | 2022-06-09 12:00~13:00 | ||||
연사 | 현동훈 (서울대) | ||||
장소 | 온라인 | ||||
제목: An algebro-geometric approach to computational complexity 초록: An algebro-geometric approach to computational complexity 초록: In this talk, I will describe a moduli-theoretic approach to problems in computational complexity theory. By simulating Turing machines with polynomial maps, we may describe Turing machine computations as algebraic maps between ind-varieties. This leads to 'moduli spaces' of polynomial time (non)deterministic Turing machines, as well as spaces parametrizing (non)deterministic polynomial time problems. I will explain how one can explicitly write down polynomial equations defining these spaces. This gives a mathematical framework for studying various problems in computational complexity, such as P vs NP. zoom ID: 313 252 8553 |