Timeline for Solving SAT correctly on all but $poly(m)$ formulas
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 2, 2017 at 16:53 | comment | added | chi | @chelsea the intuition is that at most $poly(m')$ of these tests might have the wrong result by hypothesis. This means that at least $poly(m')+1$ must have the correct result. Hence the majority of the results are correct, so we only need to count the result and follow the majority. The trick is: we have a broken machine that might be wrong on at most $N$ cases, but we know how to perform $2N+1$ queries that would have the same result on another "perfect" machine. Still, we can retrieve what the right result is by a majority argument. | |
| Nov 2, 2017 at 16:34 | vote | accept | chelsea | ||
| Nov 2, 2017 at 16:33 | comment | added | chelsea | @chi.. Thanks. Can you please explain why $2poly(m')+1$ tests suffice? | |
| Nov 2, 2017 at 14:56 | comment | added | chi | @chelsea I'm only appending $\land p$ to the original formula, leaving it as it is. No CNF involved, I'm just adding one clause at the end. I just choose $p$ to be an unused variable, in many (polynomally bounded) ways. | |
| Nov 2, 2017 at 14:26 | comment | added | chelsea | @chi can you shed some light on how to rewrite any $\phi$ in an equi-satisfiable way as you have shown? Are you trying to convert it into CNF-form with exponential number of clauses? | |
| Nov 1, 2017 at 17:52 | vote | accept | chelsea | ||
| Nov 2, 2017 at 14:26 | |||||
| Nov 1, 2017 at 14:01 | history | edited | chi | CC BY-SA 3.0 | added 92 characters in body |
| Nov 1, 2017 at 13:39 | history | edited | chi | CC BY-SA 3.0 | added 14 characters in body |
| Nov 1, 2017 at 13:34 | comment | added | chi | @Ariel Thank you! I indeed missed that point. However, it is enough to test for $2 poly(m')+1$ instances: on these only $poly(m')$ can be wrong, hence the majority decides the outcome. So, at least there's a fix. | |
| Nov 1, 2017 at 13:32 | history | undeleted | chi | ||
| Nov 1, 2017 at 13:32 | history | edited | chi | CC BY-SA 3.0 | added 108 characters in body |
| Nov 1, 2017 at 13:27 | history | deleted | chi | via Vote | |
| Nov 1, 2017 at 9:53 | comment | added | Ariel | What do you do when you see both positive and negative answers? | |
| Nov 1, 2017 at 9:40 | history | answered | chi | CC BY-SA 3.0 |