Bitcoin mining (faktorizace)

Marek Peca marek na duch.cz
Středa Duben 10 23:31:14 CEST 2013


> Ja jsem SHA-256 nikdy nezkoumal, takze nevim, jak presne funguje, ale 
> kazdopadne NP-complete problemy P resi v O(N), kdezto QC v O(sqrt(N)) - 
> kde N je pocet stavu takze zase celkem brutalni rozdil.

1. Neni jiste, ze klasicky komp neumi NP-uplne veci v O(poly), ale 
rekneme, ze tomu tak nejak verime... (Dukaz je jednim ze 6 zbyvajicich 
problemu tisicileti z puvodnich 7, ale to je asi znamo.)

2. Patrne se shodujete s mou ucebnici QC na tom, ze neni znamo, zda kdy 
bude QC schopen resit NP-uplne veci v O(poly).

3. Zda je mezi O(2^n) a O(2^sqrt(n)) rozdil pro praxi podstatnej, to si 
nejsem uplne jist. Ano, pomerove to rozdil je, ale zda to nejakou realne 
zajimavou ulohu priblizi z mnoziny "do konce sveta to nestihnem" do 
mnoziny "stihnem", to by me fakt zajimalo.

Kazdopadne QC fandim, nakolik o nich zatim nic moc nevim. Ale uz ty 
samotne stavebni bloky jsou zajimave. Je pekne, ze vlastne libovolna digi 
funkce se da spocitat obyc. linearnimi transformacemi.


ZdraviM.P.


Další informace o konferenci Hw-list