Timeline for Complexity of validity problem for Monadic First Order Logic?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 26, 2015 at 20:03 | vote | accept | Dustin Wehr | ||
| Oct 26, 2015 at 19:03 | comment | added | Marzio De Biasi | @EmilJeřábek: thanks! fixed and undeleted | |
| Oct 26, 2015 at 18:33 | history | undeleted | Marzio De Biasi | ||
| Oct 26, 2015 at 18:33 | history | edited | Marzio De Biasi | CC BY-SA 3.0 |
suggested fix by Emil
|
| Oct 26, 2015 at 16:54 | history | deleted | Marzio De Biasi | via Vote | |
| Oct 26, 2015 at 15:54 | comment | added | Emil Jeřábek | The linked papers actually suggest the problem is coNEXP-complete. The NEXP-completeness results are for satisfiability rather than validity. | |
| Oct 26, 2015 at 15:34 | history | answered | Marzio De Biasi | CC BY-SA 3.0 |