crypto course

[109]

на самом деле полезный, хотя бы даже чисто из-за используемых нотаций.

например, вместо чисто-математического равенства A = B, которое часто непонятно как использовать на практике, вводится нотация

A ≈_p B

что означает, что A computationally indistinguishable from B in polynomial time.

Comments

[plakhov.livejournal.com]

Прикольно, а это ведь нетранзитивное отношение. Можно, например, придумать три MAX-3SAT задачи A, B и С такие, что лучший результат для A неотличим от лучшего результата для В, а рез-т для В неотличим от рез-та для С, но при этом точно известно, что А меньше С.