-ДӘРІС. Детерминенделген алгоритмдер

    Полиномиалды және экспоненциалды күрделіліктерді шартты түрде бейнелейік (1-сурет).

   "Ханой мұнаралары" ойынындағы ауыстырулар үшін O(2ⁿ) амал қажет, ал матрицаларды көбейту үшін O(n³) амалдан артық емес.

   P полиномиалды және ЕХР экспоненциалды күрделіліктегі есептердің арасындағы шекара қалай өтеді? Осы сұрақтың жауабы әлі белгісіз. Шекараны айқындау үшін математиктер тағы да есептер класын ойлап тапты - NP. Интуитивті түрде бұл «шекараны бұзушы» болып есептелінеді. Бұл есептер класы (P) полиномиалды уақытта бірпроцессорлы машинадан гөрі мықтырақ – детерминирленбеген есептеуіште орындауға болатын есептер класы. Детерминирленбеген есептеуіш детерминирленбеген алгоритмдерді орындайды. Детерминирленгендік қасиетін еске түсірейік: алгоритмнің анықтылығы (детерминирленгендігі) мынаны білдіреді: әрбір қадам үшін бастапқы мәліметтер жиынтығы үшін мбірмәнді есептелінетін қадам нәтижелері де болады, және де осы нәтижелер ешқандай кездейсоқ факторларға тәуелді емес. Осыған байланысты тұтас алгоритм де белгілі жұмысы аяқталған соң нәтиже береді.

Детерминирленбеген алгоритмде бұл қасиет жоқ. Бірмәнді емес нәтижелі қадамдарды орындаймыз – бір айнымалы үшін бірнеше мән беретін қадамдарды. Бұл бірнеше мәндер ары қарай екі тәсілдің біреуімен орындалады.

    Бірінші тәсіл. Бірнеше параллель орындалатын процесстерді құрайық. Бұл параллель орындалатын процессорлары бар көппроцессорлы машинада мүмкін болады.

    Мысалы a_i санының n қосындысын орындайық. Бірпроцессорлы машинада (n-1) қосу амалын орындауға туракеледі. Бірінші қадамда a₁ + a₂, a₃ + a₄, ... қос-қостан қосуға болады. Содан кейін тағы да қос-қостан қосайық. Бұл да нәтиже болады. log₂n қадам болатынын есептеу қиын емес.