Кіріспе
Компьютер шеше алатын проблема. Теориялық компьютерлік ғылымда есептеу проблемасы – алгоритм арқылы шешілетін проблема. Мысалы, "Оң бүтін сан n берілгенде, n-нің тривиалды емес жай көбейткішін табыңыз" деген факторлау мәселесі есептеу проблемасы болып табылады. Есептеу проблемасын әрбір мысал/жағдай үшін шешімдер жиынтығы (бос болуы мүмкін) бар мысалдар немесе жағдайлар жиынтығы ретінде қарастыруға болады. Мысалы, факторлау мәселесінде мысалдар – n бүтін сандары, ал шешімдер – n-нің тривиалды емес жай көбейткіштері болып табылатын p жай сандары. Есептеу проблемалары теориялық компьютерлік ғылымдағы негізгі зерттеу нысандарының бірі болып табылады. Есептеу күрделілігі теориясы белгілі бір мәселені шешу үшін қажетті ресурстардың (есептеу күрделілігі) мөлшерін анықтауға және кейбір проблемалардың неге шешілмейтінін немесе анықталмайтынын түсіндіруге тырысады. Есептеу проблемалары күрделік сыныптарына жатады, олар оларды әртүрлі абстрактілі машиналармен есептеу (шешу) үшін қажетті ресурстарды (мысалы, уақыт, кеңістік/жад, энергия, тізбек тереңдігі) анықтайды. Мысалы, күрделік сыныптары: P – детерминистік классикалық машиналар үшін полиномиалдық уақытты тұтынатын проблемалар; BPP – ықтималдық классикалық машиналар үшін полиномиалдық уақытты тұтынатын проблемалар (мысалы, кездейсоқ сандар генераторлары бар компьютерлер); BQP – ықтималдық кванттық машиналар үшін полиномиалдық уақытты тұтынатын проблемалар. Мысалдар мен шешімдер {0, 1}* элементтері – бинарлық тізбектермен бейнеленеді. Мысалы, натурал сандар көбінесе екілік кодтау арқылы бинарлық тізбектер ретінде бейнеленеді. Бұл маңызды, себебі күрделік кіріс дерегінің ұзындығының функциясы ретінде өрнектеледі.
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
"Given a positive integer n, find a nontrivial prime factor of n."
is a computational problem. A computational problem can be viewed as a set of instances or cases together with a, possibly empty, set of solutions for every instance/case. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that are the nontrivial prime factors of n.
Computational problems are one of the main objects of study in theoretical computer science. The field of computational complexity theory attempts to determine the amount of resources (computational complexity) solving a given problem will require and explain why some problems are intractable or undecidable. Computational problems belong to complexity classes that define broadly the resources (e. g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with various abstract machines. For example, the complexity classes
P, problems that consume polynomial time for deterministic classical machines
BPP, problems that consume polynomial time for probabilistic classical machines (e. g. computers with random number generators)
BQP, problems that consume polynomial time for probabilistic quantum machines. Both instances and solutions are represented by binary strings, namely elements of {0, 1}*. For example, natural numbers are usually represented as binary strings using binary encoding. This is important since the complexity is expressed as a function of the length of the input representation.
Шешім проблемасы
Шешімдік мәселе – әрбір мысал үшін жауабы «иә» немесе «жоқ» болатын есептеу мәселесі. Шешімдік мәселеге мысал – жай сан тестілеу: «Оң бүтін сан n берілген болса, n жай сан екенін анықтаңыз». Шешімдік мәселе әдетте жауабы «иә» болатын барлық мысалдардың жиынтығы ретінде көрсетіледі. Мысалы, жай сан тестілеуін шексіз жиынтық L = {2, 3, 5, 7, 11, …} ретінде көрсетуге болады.
"Given a positive integer n, determine if n is prime." A decision problem is typically represented as the set of all instances for which the answer is yes. For example, primality testing can be represented as the infinite set
L = {2, 3, 5, 7, 11, }
Іздеу мәселесі
Іздеу мәселесінде жауаптар кез келген жолдар болуы мүмкін. Мысалы, санның жай көбейткіштерін табу – бұл іздеу мәселесі, онда мысалдар оң бүтін сандардың (жол түрінде) және шешімдер жай сандардың жиынтығының (жол түрінде) өрнектері болып табылады. Іздеу мәселесі барлық мысал-шешім жұптарынан тұратын қатынас ретінде көрсетіледі, бұл қатынас іздеу қатынасы деп аталады. Мысалы, санның жай көбейткіштерін табу келесі R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)} қатынасы арқылы бейнеленуі мүмкін, мұнда p – n санының жай көбейткіші.
R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5) }
which consist of all pairs of numbers (n, p), where p is a prime factor of n.
Санау мәселесі
Санау мәселесі берілген іздеу мәселесінің шешімдерінің санын анықтауды талап етеді. Мысалы, көбейткіштерге қатысты санау мәселесі мынадай:
"Given a positive integer n, count the number of nontrivial prime factors of n."
A counting problem can be represented by a function f from {0, 1}* to the nonnegative integers. For a search relation R, the counting problem associated to R is the function
fR(x) = |{y: R(x, y) }|.
"Оң бүтін сан n берілген болса, n-нің тривиалды емес жай көбейткіштерінің санын санаңыз."
"Given a positive integer n, count the number of nontrivial prime factors of n."
A counting problem can be represented by a function f from {0, 1}* to the nonnegative integers. For a search relation R, the counting problem associated to R is the function
fR(x) = |{y: R(x, y) }|.
Санау мәселесін {0, 1}* жиынынан теріс емес бүтін сандарға дейінгі f функциясы арқылы көрсетуге болады. R іздеу қатынасы үшін, R-мен байланысты санау мәселесі fR(x) = |{y: R(x, y)}| функциясы болып табылады.
"Given a positive integer n, count the number of nontrivial prime factors of n."
A counting problem can be represented by a function f from {0, 1}* to the nonnegative integers. For a search relation R, the counting problem associated to R is the function
fR(x) = |{y: R(x, y) }|.
Оптимизациялау мәселесі
Оптимизациялау мәселесі іздеу мәселесінің барлық мүмкін шешімдері ішінде "ең жақсы" шешімді табуды талап етеді. Мысалы, ең үлкен тәуелсіз жиынтық мәселесі: "G графы берілген, G-нің ең үлкен тәуелсіз жиынтығын табыңыз". Оптимизациялау мәселелері мақсаттық функциясы және шектеулері арқылы сипатталады.
"Given a graph G, find an independent set of G of maximum size." Optimization problems are represented by their objective function and their constraints.
Функционалдық мәселе
Функциялық мәселеде әрбір кіріс үшін жалпы функцияның бір ғана шығысы күтіледі, бірақ бұл шығыс шешімдік мәселеге қарағанда күрделірек, яғни ол жай ғана "иә" немесе "жоқ" емес. Ең әйгілі мысалдардың бірі – саяхатшы саудагерінің мәселесі: "Қалалар тізімі және әрбір қала жұбы арасындағы қашықтық берілген жағдайда, әр қалаға бір рет барып, бастапқы қалаға оралатын ең қысқа маршрутты табыңыз". Бұл комбинаторлық оптимизациядағы NP-қиын мәселе болып табылады және операциялық зерттеулер мен теориялық информатикада маңызды рөл атқарады.
"Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city." It is an NP hard problem in combinatorial optimization, important in operations research and theoretical computer science.