| (06-09 12:00) [강연회] An algebro-geometric approach to computational complexity | |||||
| 작성자 | 과사무실 | ||||
|---|---|---|---|---|---|
| 조회수 | 904 | 등록일 | 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 |
|||||