Timeline for An NP-complete variant of factoring.
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2011 at 23:33 | comment | added | Tsuyoshi Ito | The SHORT PROOFS problem in the paper is almost the same as the bounded halting problem. A reduction from the SHORT PROOFS problem would be most likely as messy as the typical proof of the NP-completeness of SAT, and therefore it is unlikely that the proof of the NP-completeness of this factor finding problem by Kilian constructs a reduction from the SHORT PROOFS problem directly. | |
| Mar 2, 2011 at 17:47 | comment | added | Marzio De Biasi | @Marc ... mmm ... I think that it means: $\{\langle L, U, N \rangle \;|\; (\exists p \in \{L, \ldots, U\})[p | N]\}$ is NP-complete because a polynomial reduction from the NP-complete problem SHORT PROOF exists ... | |
| Mar 2, 2011 at 15:53 | comment | added | Marc Bury | This is just another formulation that this problem is NP-complete. | |
| Mar 1, 2011 at 21:09 | history | answered | Marzio De Biasi | CC BY-SA 2.5 |