ќракульна модель. ќпишемо пон¤тт¤ оракульного алгоритму. ÷е абстрактна обчислювальна модель, ¤ка не описуЇ н≥¤ких рельних обчислень, а потрубна нам дл¤ пор≥вн¤нн¤ обчислювальноњ складност≥ задач.

ѕ≥д оракулом ми будемо розум≥ти будь-¤ку функц≥ю , де та - ск≥нченн≥ алфав≥ти. ќракульний алгоритм Ї алгоритмом у звичному розум≥нн≥, але над≥лений додатковою елементарною операц≥Їю зверненн¤ до† оракула. ÷¤ операц≥¤ виконуЇтьс¤ зразу п≥сл¤ того, ¤к алгоритм в результат≥ своЇњ попередньоњ роботи надрукував де¤ке слово , що називаЇтьс¤ запитом до оракула. ¬насл≥док зверненн¤ до оракула †алгоритм отримуЇ слово , в≥дпов≥дь оракула, ¤ке використовуЇтьс¤ у подальш≥й робот≥. ќракульний алгоритм ≥з доступом до оракула †позначатимемо через . «ауважимо,що робота оракульного алгоритму може суттЇво залежати в≥д того, до ¤кого конкретно оракула в≥н маЇ доступ.

††††††††††† як приклад наведемо щонайпрост≥ший алгоритм з доступом до оракула .

††††††††††† јлгоритм

Ј         отримуЇ на вх≥д слово .

Ј         звертаЇтьс¤ до оракла ≥з запитом ;

Ј         подаЇ на вих≥д .

«розум≥ло, що †обчислюЇ функц≥ю . ÷ей приклад демонструЇ наск≥льки широкими (≥ нереал≥стичними) Ї можливост≥ орак≥льних алгоритм≥в пор≥вн¤но ≥з звичайними Ц оракульний алгоритм може очислити нав≥ть таку функц≥ю, ¤ку не можна обчислити н≥¤ким звичайним алгоритмом, варто лише вз¤ти достатньо УпотужнийФ оракул.

ѕон¤тт¤ часу роботи поширюЇтьс¤ на оракульн≥ алгоритм膆††††††† зг≥дно ≥з домовлен≥стю, що зверненн¤ до оракула займаЇ лише один крок. јле окремо сл≥д враховувати час, ¤кий затрачаЇтьс¤ на друкуванн¤ запиту та зчитуванн¤ в≥дпов≥д≥ оракула. ќракульний алгоритм називаЇтьс¤ пол≥ном≥альним, ¤кщо в≥н працюЇ час, обмежений де¤ким пол≥номом в≥д довжини входу, причому це обмеженн¤ виконуЇтьс¤ дл¤ кожного оракула. «верненн¤ до оракулаприподно ≥нтерпретувати у програм≥стських терм≥нах ¤к вмклик програмою п≥дпроцедури, що обчислюЇ функц≥ю на заданому аргумент≥, причому час роботи процедури не враховуЇтьс¤ при оц≥нц≥ загального часу програми.

ќракул , що Ї характеристичною функц≥Їю де¤коњ множини , будемо утотожнювати ≥з самою множиною ≥ писати зам≥сть .