Timeline for Is following SAT case in $\mathsf{P}$?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2017 at 7:51 | vote | accept | rus9384 | ||
| Jun 9, 2017 at 4:47 | history | edited | Raphael |
edited tags
|
|
| Jun 8, 2017 at 22:07 | answer | added | Yuval Filmus | timeline score: 1 | |
| Jun 8, 2017 at 22:01 | comment | added | rus9384 | I mean that generally every subformula would have at most half positive assignments. So, it seems that I reduce it to 2-SAT (2 formulas). They are prior and then I can proceed with other subformulas. | |
| Jun 8, 2017 at 21:51 | comment | added | Yuval Filmus | The class $\mathsf{P}$ is a property of problems or languages, not of instances. Every instance can be solved correctly in $O(1)$ by some algorithm. | |
| Jun 8, 2017 at 21:47 | history | asked | rus9384 | CC BY-SA 3.0 |