|
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might be able to solve. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computational problem. Computational problems are one of the main objects of study in theoretical computer science. The field of algorithms studies methods of solving computational problems efficiently. The complementary field of computational complexity attempts to explain why certain computational problems are intractable for computers. A computational problem can be viewed as an infinite collection of ''instances'' together with a ''solution'' for every instance. For example, in the factoring problem, the instances are the integers ''n'', and solutions are prime numbers ''p'' that describe nontrivial prime factors of ''n''. It is conventional to represent both instances and solutions by binary strings, namely elements of *. For example, numbers can be represented as binary strings using the binary encoding. (For readability, we identify numbers with their binary encodings in the examples below.) ==Types of computational problems== A decision problem is a computational problem where the answer for every instance is either yes or no. An example of a decision problem is ''primality testing'': :"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'' = In a search problem, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes. A search problem is represented as a relation consisting of all the instance-solution pairs, called a ''search relation''. For example, factoring can be represented as the relation :''R'' = which consist of all pairs of numbers (''n'', ''p''), where ''p'' is a nontrivial prime factor of ''n''. A counting problem asks for the number of solutions to a given search problem. For example, a counting problem associated with factoring is :"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 * to the nonnegative integers. For a search relation ''R'', the counting problem associated to ''R'' is the function :''fR''(x) = ||. An optimization problem asks for finding a "best possible" solution among the set of all possible solutions to a search problem. One example is the ''maximum independent set'' problem: :"Given a graph ''G'', find an independent set of ''G'' of maximum size." Optimization problems can be represented by their search relations. In a function problem a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just "yes" or "no". One of the most famous examples is the ''travelling salesman'' problem: :"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. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Computational problem」の詳細全文を読む スポンサード リンク
|