Tudunk gyorsan egyenletes eloszlásban számot generálni mod 3 vagy NP-beli problémát megoldani?
| Témavezető: | Pálvölgyi Dömötör |
| ELTE TTK, Számítógéptudományi Tanszék | |
| email: | domotor.palvolgyi@ttk.elte.hu |
Projekt leírás
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.