Timeline for Is #k-XORSAT #P-complete?
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 7, 2010 at 15:11 | history | edited | Peter Shor | CC BY-SA 2.5 |
clarified after looking at Andrea's answer
|
| Aug 14, 2010 at 23:47 | history | edited | Peter Shor | CC BY-SA 2.5 |
added 51 characters in body
|
| Aug 14, 2010 at 21:00 | comment | added | András Salamon | I'll edit the question to remove this source of confusion. | |
| Aug 14, 2010 at 20:53 | comment | added | Qiaochu Yuan | Ah, thanks. I was confused by the remark about problems solvable in linear time leading to #P-complete problems, but now I see that the remark was about problems whose decision versions are solvable in linear time and whose counting versions are #P-complete. | |
| Aug 14, 2010 at 20:40 | comment | added | Tsuyoshi Ito | @Qiaochu: Peter’s answer explains how to compute the number of the solutions to any given instance of the XORSAT problem in polynomial time (and k-XORSAT is a special case of XORSAT). Therefore, yes, it implies that the counting version of k-XORSAT is not #P-complete — unless the whole #P is computable in polynomial time! | |
| Aug 14, 2010 at 20:35 | comment | added | András Salamon | The way I understand Peter's answer, yes: compute the rank $r$ of the system, then the answer is $2^r$. As the rank is at most $k$, a constant, this can be computed in polynomial time. | |
| Aug 14, 2010 at 20:14 | comment | added | Qiaochu Yuan | Sorry for the stupid question, but does this immediately imply that k-XORSAT is not #P-complete? | |
| Aug 14, 2010 at 19:54 | vote | accept | András Salamon | ||
| Aug 14, 2010 at 19:52 | vote | accept | András Salamon | ||
| Aug 14, 2010 at 19:53 | |||||
| Aug 14, 2010 at 19:49 | history | answered | Peter Shor | CC BY-SA 2.5 |