Yes/no problem in computer science
decision problems in complexity theory
Есептеу теориясы және есептеу күрделілігі теориясында шешімдік есеп – кіріс мәндеріне «иә» немесе «жоқ» түрінде берілетін есептеу проблемасы. Шешімдік есепке мысал – берілген натурал санның жай сан екенін алгоритм арқылы анықтау. Тағы бір мысал: «Егер x және y екі сан берілсе, x саны y санын қалдықсыз бөледі ме?» деген сұрақ. Жауап x және y мәндеріне байланысты «иә» немесе «жоқ» болады. Алгоритм түрінде берілген шешімдік есепті шешу әдісі – сол есептің шешімдік процедурасы деп аталады. «x және y екі сан берілсе, x саны y санын қалдықсыз бөледі ме?» деген шешімдік есеп үшін шешімдік процедура x-тің y-ді қалдықсыз бөлетінін анықтау үшін қадамдарды көрсетеді. Мұндай алгоритмдердің бірі – ұзын бөлу. Егер қалдық нөл болса, жауап «иә», әйтпесе «жоқ» болады. Алгоритммен шешілетін шешімдік есеп – шешімдік есеп деп аталады. Шешімдік есептер көбінесе математикалық шешімділік мәселелерінде кездеседі, яғни кейбір объектінің бар екенін немесе жиынға кіретінін анықтау үшін тиімді әдіс бар ма деген сұрақтарда; математикадағы маңызды проблемалардың кейбіреулері шешілмейді. Есептеу күрделілігі саласы шешімдік есептерді шешудің қиындығына қарай жіктейді. «Қиындық» осы есеп үшін ең тиімді алгоритмге қажетті есептеу ресурстарымен сипатталады. Ал рекурсиялық теория шешілмейтін шешімдік есептерді Тьюринг дәрежесі бойынша жіктейді, ол кез келген шешімге тән есептеу мүмкін еместігінің өлшемі болып табылады.
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called decidable. Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set; some of the most important problems in mathematics are undecidable. The field of computational complexity categorizes decidable decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem. The field of recursion theory, meanwhile, categorizes undecidable decision problems by Turing degree, which is a measure of the noncomputability inherent in any solution.
Анықтама
Шешімдік мәселе – шексіз кіріс жиынына қойылатын "иә" немесе "жоқ" сұрағы. Шешімдік мәселені мүмкін кірістер жиыны және жауабы "иә" болатын кірістер жиыны ретінде анықтау қалыпты жағдай. Бұл кірістер табиғи сандар болуы мүмкін, бірақ екілік тізбектер немесе басқа әліпбидегі тізбектер сияқты басқа да түрлерде де болуы мүмкін. Мәселе "иә" деп жауап беретін тізбектердің ішкі жиыны формальді тіл болып табылады, ал шешімдік мәселелер көбінесе формальді тілдер ретінде беріледі. Гёдель нөмірлеуі сияқты кодтаудың көмегімен кез келген тізбекті табиғи санға түрлендіруге болады, осылайша шешімдік мәселені табиғи сандардың ішкі жиыны ретінде анықтауға болады. Демек, шешімдік мәселенің алгоритмі – табиғи сандардың ішкі жиынының сипаттамалық функциясын есептеу.
A decision problem is a yes or no question on an infinite set of inputs. It is traditional to define the decision problem as the set of possible inputs together with the set of inputs for which the answer is yes. These inputs can be natural numbers, but can also be values of some other kind, like binary strings or strings over some other alphabet. The subset of strings for which the problem returns "yes" is a formal language, and often decision problems are defined as formal languages. Using an encoding such as Gödel numbering, any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. Therefore, the algorithm of a decision problem is to compute the characteristic function of a subset of the natural numbers.
Мысалдар
Шешімді проблеманың классикалық мысалы – жай сандар жиыны. Кез келген берілген натурал санның жай екенін оның барлық мүмкін бөлгіштерін тексеру арқылы анықтауға болады. Жайлықты тексерудің әлдеқайда тиімді әдістері белгілі болғанымен, кез келген тиімді әдіс болуы шешімділігін дәлелдеу үшін жеткілікті.
A classic example of a decidable decision problem is the set of prime numbers. It is possible to effectively decide whether a given natural number is prime by testing every possible nontrivial factor. Although much more efficient methods of primality testing are known, the existence of any effective method is enough to establish decidability.
Шешімділік
Шешімдік мәселе шешіледі немесе тиімді шешіледі, егер жауабы «иә» болатын кірістер (немесе натурал сандар) жиыны рекурсивті жиын болса. Мәселе ішінара шешіледі, жартылай шешіледі, шешіледі немесе дәлелденеді, егер жауабы «иә» болатын кірістер (немесе натурал сандар) жиыны рекурсивті санамалы жиын болса. Шешілмейтін мәселелер шешілмейді. Оларды шешу үшін тиімді немесе басқа да алгоритм жасау мүмкін емес. Тоқтау мәселесі – маңызды шешілмейтін шешімдік мәселе; толық мысалдар үшін шешілмейтін мәселелер тізілімін қараңыз.
A decision problem is decidable or effectively solvable if the set of inputs (or natural numbers) for which the answer is yes is a recursive set. A problem is partially decidable, semidecidable, solvable, or provable if the set of inputs (or natural numbers) for which the answer is yes is a recursively enumerable set. Problems that are not decidable are undecidable. For those it is not possible to create an algorithm, efficient or otherwise, that solves them. The halting problem is an important undecidable decision problem; for more examples, see list of undecidable problems.
Толық проблемалар
Шешімдерді анықтау мәселелері көптеген бір редукцияға сәйкес реттелген және полиномиалдық уақыт редукциясы сияқты қолданылатын редукциялармен байланысты. Егер P мәселесі S мәселелер жиымының құрамында болса және S жиымындағы әрбір мәселені P-ге дейін редукциялау мүмкін болса, онда P шешімдерді анықтау мәселесі S жиымы үшін толық деп аталады. Толық шешімдерді анықтау мәселелері есептеу күрделілігі теориясында шешімдерді анықтау мәселелерінің күрделілік кластарын сипаттау үшін қолданылады. Мысалы, Бульдік қанағаттандыру мәселесі полиномиалдық уақыт редукциясы бойынша шешімдерді анықтау мәселелерінің NP класы үшін толық.
Decision problems can be ordered according to many one reducibility and related to feasible reductions such as polynomial time reductions. A decision problem P is said to be complete for a set of decision problems S if P is a member of S and every problem in S can be reduced to P. Complete decision problems are used in computational complexity theory to characterize complexity classes of decision problems. For example, the Boolean satisfiability problem is complete for the class NP of decision problems under polynomial time reducibility.
Функционалдық мәселелер
Шешім қабылдау проблемалары функциялық проблемалармен тығыз байланысты, олардың жауаптары қарапайым "иә" немесе "жоқ" дегеннен күрделірек болуы мүмкін. Функциялық проблеманың сәйкес мысалы: "екі сан x және y берілгенде, x-ті y-ға бөлгенде не шығады?". Функциялық проблема бөлшектік функция f-ден тұрады; бұл функцияның анықталған кірістері үшін f-тің мәнін есептеу болып табылады. Кез келген функциялық проблеманы шешім қабылдау проблемасына айналдыруға болады; шешім қабылдау проблемасы – бұл байланысты функцияның графигі. (Функцияның f графигі – f(x) = y болатын (x, y) жұптарының жиыны.) Егер бұл шешім қабылдау проблемасы тиімді шешілсе, онда функциялық проблема да тиімді шешіледі. Алайда, бұл түрлендіру есептеу күрделілігін ескермейді. Мысалы, функцияның графигі полиномиалдық уақытта шешілуі мүмкін (яғни, орындалу уақыты (x, y) жұбының функциясы ретінде есептеледі), ал функция полиномиалдық уақытта есептелмейді (яғни, орындалу уақыты тек x-тің функциясы ретінде есептеледі). f(x) = 2x функциясы осы қасиетке ие. Кез келген шешім қабылдау проблемасын, осы проблемаға байланысты жиынның сипаттамалық функциясын есептеудің функциялық проблемасына түрлендіруге болады. Егер бұл функция есептелетін болса, онда байланысты шешім қабылдау проблемасы шешіледі. Дегенмен, бұл түрлендіру есептеу күрделілігінде қолданылатын стандартты түрлендіруден (кейде "көп біріне айналдыру" деп аталады) көбірек еркін; мысалы, NP-толық проблеманың және оның ко-NP-толық толықтыруының сипаттамалық функцияларының күрделілігі бірдей болады, тіпті негізгі шешім қабылдау проблемалары кейбір есептеу модельдерінде эквивалентті болып саналмауы мүмкін.
Decision problems are closely related to function problems, which can have answers that are more complex than a simple 'yes' or 'no'. A corresponding function problem is "given two numbers x and y, what is x divided by y?". A function problem consists of a partial function f; the informal "problem" is to compute the values of f on the inputs for which it is defined. Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. (The graph of a function f is the set of pairs (x,y) such that f(x) = y.) If this decision problem were effectively solvable then the function problem would be as well. This reduction does not respect computational complexity, however. For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair (x,y)) when the function is not computable in polynomial time (in which case running time is computed as a function of x alone). The function f(x) = 2x has this property. Every decision problem can be converted into the function problem of computing the characteristic function of the set associated to the decision problem. If this function is computable then the associated decision problem is decidable. However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial time many one reduction); for example, the complexity of the characteristic functions of an NP complete problem and its co NP complete complement is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.
Оптимизациялау проблемалары
Шешім проблемаларынан өзгеше, әрбір кіріс үшін тек бір дұрыс жауап болатын, оңтайландыру проблемалары белгілі бір кіріске ең жақсы жауапты табумен айналысады. Оңтайландыру проблемалары көптеген қолданыстарда, мысалы, саяхатшы сатушысының мәселесі және сызықтық бағдарламалаудағы көптеген сұрақтар сияқты жағдайларда табиғи түрде туындайды. Функциялық және оңтайландыру проблемалары жиі шығыс белгілі бір мәнге тең немесе одан кем-көп екенін қарастыру арқылы шешім проблемаларына түрлендіріледі. Бұл сәйкес шешім проблемасының күрделілігін зерттеуге мүмкіндік береді; және көптеген жағдайларда бастапқы функциялық немесе оңтайландыру проблемасын оның сәйкес шешім проблемасын шешу арқылы шешуге болады. Мысалы, саяхатшы сатушысының мәселесінде оңтайландыру проблемасы – ең төмен салмақты тур жасау. Оған қатысты шешім проблемасы: әрбір N үшін, графикте N-ден кем салмағы бар тур бар ма, жоқ па, анықтау. Шешім проблемасын қайта-қайта шешу арқылы турдың ең төмен салмағын табуға болады. Шешім проблемаларының теориясы өте жақсы дамығандықтан, күрделік теориясындағы зерттеулер көбінесе шешім проблемаларына бағытталған. Оңтайландыру проблемаларының өзі есептеу теориясында, сондай-ақ операциялық зерттеулер сияқты салаларда әлі де қызығушылық тудырады.
Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding the best answer to a particular input. Optimization problems arise naturally in many applications, such as the traveling salesman problem and many questions in linear programming. Function and optimization problems are often transformed into decision problems by considering the question of whether the output is equal to or less than or equal to a given value. This allows the complexity of the corresponding decision problem to be studied; and in many cases the original function or optimization problem can be solved by solving its corresponding decision problem. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each N, to decide whether the graph has any tour with weight less than N. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour. Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as operations research.