Timeline for Best known algorithm for NEXP-complete problem
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 30, 2022 at 10:44 | comment | added | Reijo Jaakkola | And I was referring to your term "syntactic complexity parameter". | |
| May 30, 2022 at 10:41 | comment | added | Emil Jeřábek | I wrote “such as”. | |
| May 30, 2022 at 10:37 | comment | added | Reijo Jaakkola | I don't think it makes sense to argue about whether or not $\mathcal{L}$ is really a logic, because --- as you pointed out --- the term is quite vague. Note that the sketch of a definition you proposed does not seem to include several natural (decidable) fragments of FO such as the guarded fragment (quantification should be relativized) or unary negation fragment (negation can only be applied to formulas with at most one free variable). | |
| May 30, 2022 at 10:28 | comment | added | Emil Jeřábek | I seriously doubt anyone (and authors of that paper in particular) would consider the language you defined to be a “logic”. While the term is vague, in this context it generally denotes fragments of FO or SO obtained by restricting some syntactic complexity parameters such as quantifier alternation, number of variables, or arity of relations. It’s not used as a synonym for “arbitrary set of formulas”. | |
| May 30, 2022 at 9:58 | history | edited | Reijo Jaakkola | CC BY-SA 4.0 |
added 1164 characters in body
|
| May 30, 2022 at 9:13 | history | edited | Reijo Jaakkola | CC BY-SA 4.0 |
added 206 characters in body
|
| May 30, 2022 at 8:36 | comment | added | Emil Jeřábek | No, they do not say they were not aware of any previous algorithms on NExpTime-complete problems that had a run time which was significantly lower than $2^{2^n}$. They say “to the best of our knowledge, these are the first exact algorithms for an NEXP-complete decidable logic with run time significantly lower than $O(2^{2^n})$”. That’s quite a different statement, as it only concerns a handful of problems of a very specific nature, not arbitrary NEXP-complete problems. As I already pointed out above, extending the claim to all NEXP-complete problems is plain nonsense. | |
| May 30, 2022 at 8:14 | vote | accept | Alexey Milovanov | ||
| May 30, 2022 at 13:47 | |||||
| May 30, 2022 at 7:27 | history | answered | Reijo Jaakkola | CC BY-SA 4.0 |