Timeline for What is the generic complexity of First Order Predicate Calculus?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 2, 2014 at 13:05 | comment | added | Joel David Hamkins | +1. I like this question very much. But it seems likely that the answer will depend on the details of the syntactic formalism. For example, insisting on normal forms or changing which logical connectives are allowed could conceivably affect the density of the set of validities. Also, adding extra predicate, function and constant symbols will affect density. | |
| May 26, 2014 at 13:09 | comment | added | Jim Graber | A translation of this reference might be very informative: mathnet.ru/php/… | |
| May 26, 2014 at 13:08 | comment | added | Jim Graber | Wikipedia Generic-case complexity is a good start. Three other references: homepages.ecs.vuw.ac.nz/~downey/generic_decision.pdf arxiv.org/abs/math/0504351 omskconf2009.oscsbras.ru/miasnikov2.pdf | |
| May 26, 2014 at 0:08 | comment | added | Dima Pasechnik | I guess most of the people here, myself included, have no idea about generic complexity. Care to elaborate? | |
| May 25, 2014 at 17:10 | review | First posts | |||
| May 25, 2014 at 17:11 | |||||
| May 25, 2014 at 16:53 | history | asked | Jim Graber | CC BY-SA 3.0 |