Koks yra mažinimo idėja? Atsižvelgiant į ankstesnį klausimą, parašykite kontekstą, kuriame būtų atsakymas. Tai gali būti nuo 1 iki 20 sakinių. Kontekstas:
Daugelis sudėtingumo klasių apibrėžiami naudojant redukcijos sąvoką. Sumažinimas yra vienos problemos transformacija į kitą problemą. Jis atspindi neformalią sąvoką, kad problema yra bent jau tokia pat sudėtinga, kaip ir kita problema. Pavyzdžiui, jei X problema gali būti išspręsta naudojant Y algoritmą, X nėra sunkiau nei Y, ir mes sakome, kad X sumažina į Y. Yra daug skirtingų tipų sumažinimų, pagrįstų sumažinimo metodu, pvz., Cooko sumažinimai, Karpo sumažinimai ir Levino sumažinimai, ir ribos sumažinimo sudėtingumui, pvz., Polinominio laiko sumažinimai ar logaritminės erdvės sumažinimai.