Timeline for Is there a natural restriction of VO logic which captures P or NP?
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 4, 2010 at 2:29 | history | edited | Sadeq Dousti | CC BY-SA 2.5 |
deleted 7 characters in body
|
| Oct 4, 2010 at 0:37 | comment | added | Arthur MILCHIOR | I suggest that you read section 5.3 page 34 of my paper about the problem I met on Horn and Krom in High Order logic. You will meet the same problem in Variable Order (which is clearly a superset of High Order) | |
| Oct 4, 2010 at 0:30 | comment | added | András Salamon | To be more precise, I mean a syntactic restriction along the lines of SNP, where the SO quantifiers are applied to a FO formula of specific form (for SNP, with universal FO quantifiers only), and then further restrictions are applied, such as the FO formula inside the FO quantifiers being Horn or Krom. The last paragraph of your Section 5.3 talks about this, but I don't understand your comment that the approach is problematic. | |
| Oct 3, 2010 at 22:14 | comment | added | András Salamon | Thanks for the discussion, I will look at your reformulation. Do you have any suggestions for some ways to restrict the logic so it isn't so powerful -- would something like requiring the unquantified part of the formula to be in CNF with Horn clauses likely to be useful, as it is with classical quantifiers? | |
| Oct 3, 2010 at 21:55 | history | answered | Arthur MILCHIOR | CC BY-SA 2.5 |