Hvernig hugmynd er minnkun? Skrifaðu svarið í samhengi við fyrri spurningu. Það geta verið 1 - 20 setningar. Umfjöllun:
Margir flækjustigsklassar eru skilgreindir með hugtakinu minnkun. Lækkun er breyting á einu vandamáli í annað vandamál. Það tekur óformlega hugmyndina um að vandamál sé að minnsta kosti jafn erfitt og annað vandamál. Til dæmis, ef vandamál X er hægt að leysa með því að nota algoritma fyrir Y, þá er X ekki erfiðara en Y, og við segjum að X minnki til Y. Það eru margar mismunandi tegundir af niðurfellingum, byggt á aðferðinni við niðurfellingu, svo sem Cook niðurfellingar, Karp niðurfellingar og Levin niðurfellingar, og takmörk á flóknleika niðurfellinga, svo sem fjölnefna tíma niðurfellingar eða log-rými niðurfellingar.