Andó-Kinorányi Szabolcs: Tudunk gyorsan egyenletes eloszlásban számot generálni mod 3 vagy NP-beli problémát megoldani?

Egyéni Kutatómunka 1

2020/21 II. félév

Témavezető:
Pálvölgyi Dömötör (ELTE TTK, Számítógéptudományi Tanszék)

Tegyük fel, hogy tudunk generálni egyenletes eloszlásban véletlen egész számot {1, 2, ... 2ⁿ}-ből, és kapunk egy nehéz számítási feladatot. A célunk az, hogy vagy megoldjuk a nehéz problémát, vagy adjunk egyenletes eloszlásban egy számot {1, 2, 3}-ból.