Timeline for Why is integer factoring hard while determining whether an integer is prime easy?
Current License: CC BY-SA 4.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 6, 2022 at 9:48 | comment | added | Emil Jeřábek | A much simpler example are perfect matchings in bipartite graphs: one can decide in polynomial time if such a matching exists, but counting them is #P-complete (this is the same as computing the permanent of $\{0,1\}$-matrices). | |
| Dec 6, 2022 at 7:54 | history | answered | Per Alexandersson | CC BY-SA 4.0 |