Timeline for Why can't hashes be reversed with toffoli gates?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 13, 2014 at 15:13 | vote | accept | Kartik | ||
| Feb 12, 2014 at 11:48 | history | edited | fgrieu♦ | CC BY-SA 3.0 | Also cover notation T(x) rather than T(x,z) |
| Feb 12, 2014 at 9:27 | history | edited | fgrieu♦ | CC BY-SA 3.0 | Expand and remove some conditionals since I'm now confident with the answer |
| Feb 11, 2014 at 17:10 | comment | added | Kartik | I think you're right. I'm still trying. If I can't get it till tomorrow, I will accept your answer. | |
| Feb 11, 2014 at 14:49 | comment | added | Kartik | I'm trying to do this for the function you specified. I will upload a PDF when this is done. BTW, thanks for your help. | |
| Feb 11, 2014 at 14:07 | comment | added | fgrieu♦ | @Kartik: I agree that in your example, what you wrote holds. That's because your example reduces to $H(x)=x$, which we could write with zero gates and no garbage. Problem is, you can't prove an assertion by example. You can disprove it, however. Try something a tad more complex, like $y_0=H(x)=(x_0\land\bar{x_1})\lor(\bar{x_0}\land x_1)$, which unless I err requires at least one bit of garbage. | |
| Feb 11, 2014 at 13:19 | comment | added | Kartik | I added an example. | |
| Feb 11, 2014 at 12:57 | history | edited | fgrieu♦ | CC BY-SA 3.0 | Add alternate explanation. |
| Feb 11, 2014 at 12:56 | comment | added | Kartik | Wait a minute, I'll upload an example. | |
| Feb 11, 2014 at 12:46 | comment | added | Kartik | We have reversed $T$ and got $x'$ so it should hold for any valid garbage. (Because we have got $x'$ by reversing $y,z'$) | |
| Feb 11, 2014 at 12:38 | history | undeleted | fgrieu♦ | ||
| Feb 11, 2014 at 12:37 | history | deleted | fgrieu♦ | via Vote | |
| Feb 11, 2014 at 12:36 | history | answered | fgrieu♦ | CC BY-SA 3.0 |