Fogalmak és módszerek

Próbálgatással megoldható feladatokról

Absztrakt

Ismertető cikkünk első két részében meghatározzuk a szóban forgó feladatcsaládot. A 3. részben a visszavezethetőség és az univerzalitás fogalmait definiáljuk, a 4. részben megmutatjuk, hogy van univerzális feladat, végül az 5. részben példákon mutatjuk be, hogyan lehet egy feladatról bebizonyítani, hogy ő univerzális. A Függelék a technikai részletek iránt érdeklődő olvasóknak kiegészítő információkat ad.
A közölt eredményeket az USA-ban Cook és Karp, a Szovjetunióban tőlük függetlenül L. A. Levin érte el.