Timeline for SAT and Arithmetic Geometry
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 15, 2022 at 17:56 | comment | added | Joshua Grochow | Re: Castelnuovo-Mumford regularity & complexity: see the paper "What can be computed in algebraic geometry?" by Bayer & Mumford (arxiv.org/abs/alg-geom/9304003), as well as the three papers by Bayer & Stillman it cites, esp. the intro of sciencedirect.com/science/article/pii/S0747717188800397 has a nice discussion of the role of regularity in understanding the complexity of Gröbner basis calculations. | |
| Dec 7, 2012 at 17:30 | comment | added | Camilo Sarmiento | Supporting the skepticism in (4), i once saw a talk by Anders Bjoerner, where he mentioned a "program" to prove P≠NP. He said the first step is to find a good description of a Boolean function as a variety. According to him, this would the most difficult thing to come up with (the rest being \'etale cohomology...) | |
| Dec 6, 2012 at 17:58 | comment | added | Vanessa | Thanks a lot for your answer! I want to point out that I realize very well the distinction between decidability and computability. However, my naive intuition tells me that a problem which is close to an undecidable problem must have high complexity. For example the halting problem is undecidable whereas deciding whether a program halts in k steps is EXP-complete. Deciding whether a program halts on every output is even higher in the undecidability hierarchy (I think) whereas deciding whether a program halts on every output in k steps is NEXP-complete | |
| Dec 6, 2012 at 17:32 | comment | added | Dima Pasechnik | Vakil's work actually uses Mnev's Universality Theorem, which in a way has a computational flavour. | |
| Dec 6, 2012 at 15:46 | history | answered | David E Speyer | CC BY-SA 3.0 |