Timeline for 3-SAT and a matrix of linear forms representing a non-degenerate matrix
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Dec 7, 2011 at 19:46 | history | edited | Łukasz Grabowski | CC BY-SA 3.0 |
edited title
|
| Dec 7, 2011 at 18:39 | comment | added | Emil Jeřábek | @Gerhard: As discussed in the previous question, this probabilistic algorithm only works if the size of the field is larger than the degree of the polynomial (i.e., $n$). Here, the field size is constant. | |
| Dec 7, 2011 at 18:36 | comment | added | Gerhard Paseman | Probabilistic checking of invertibility means choosing values at random and evaluating the resulting determinant and seeing if it is nonzero. This is O(n^3), with a good chance of success if there are such values. Is the 3SAT problem solved if we find such values? Gerhard "Ask Me About System Design" Paseman, 2011.12.07 | |
| Dec 7, 2011 at 18:11 | history | asked | Łukasz Grabowski | CC BY-SA 3.0 |