Timeline for The hardness of computing inverse
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 2, 2022 at 17:24 | answer | added | Joshua Grochow | timeline score: 3 | |
| Jun 21, 2011 at 15:54 | vote | accept | CommunityBot | moved from User.Id=10891 by developer User.Id=35352 | |
| Jun 21, 2011 at 12:28 | comment | added | Joel David Hamkins | So it appears that, short of a proof of $P\neq NP$, we will have only dishonest answers to this question! :-) | |
| Jun 21, 2011 at 11:39 | comment | added | François G. Dorais | Note that the definition of one-way function on Wikipedia is missing an often overlooked key requirement: honesty - that the length of the output must be nearly equal to some polynomial of the length of the input. As Joel's example shows, this requirement is essential... | |
| Jun 21, 2011 at 9:06 | comment | added | Jesko Hüttenhain | The concept is closely related to that of a one-way function, whose existence would imply $\mathrm{P}\ne\mathrm{NP}$. Link: en.wikipedia.org/wiki/One-way_function | |
| Jun 21, 2011 at 7:15 | comment | added | Gerhard Paseman | Known? Don't know. Unlikely to be known? Try an appropriate encoding that computes the encoded equivalent of f(G,k,p) = G if p is a Hamiltonian path through G of length at most k, and 0 otherwise. There are probably ways to tweak this to get something 1-1. Also, you can probably get something similar for most interesting complexity classes. Gerhard "Email Me About System Design" Paseman, 2011.06.21 | |
| Jun 21, 2011 at 7:07 | comment | added | darij grinberg | Wouldn't that immediately yield $P\neq NP$? (Unless the inverse significantly increase the length of $n$...) | |
| Jun 21, 2011 at 7:03 | history | asked | user10891 | CC BY-SA 3.0 |