In theoretical computer science, a computational problem is a mathematical object representing a question that computers might want to solve. For example, "given any number x, determine whether x is prime" is a computational problem. Computational problems are one of the main objects of study in theoretical computer science, because nearly any task we would want to accomplish is an example of a computational problem. In the field of algorithms, we study methods of solving computational problems; in the complementary field of computational complexity theory, we organize computational problems based on how difficult they are to solve. Computer science (informally, CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ... Flowcharts are often used to represent algorithms. ... In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given problem. ...

Problems and instances

A computational problem encodes a general problem, independent of its specific input. A problem with a specific set of inputs is called an instance. For example, "Given any two numbers x and y, find the sum of x and y" is a computational problem. A specific instance of that computational problem would be "What is the sum of 13 and 28?". An object is fundamental concept in object-oriented programming. ...

Formal definition

A formal definition of computational problems probably exists, and would be helpful.

Types of computational problems

Computational problems are organized in many different ways. They can be organized by how they are defined, and by how many computational resources are needed to compute an answer. Computational problems that intuitively look very similar can vary wildly in the amount of resources needed to compute them, and some computational problems are noncomputable, meaning that no possible algorithm could solve every instance.

A computational problem which only returns a yes-or-no answer is called a decision problem. Examples of decision problems include "given an integer n, determine whether n is prime" and "given two numbers x and y, determine whether x evenly divides y". Decision problems are often used in computational complexity theory, because they are easier to study than other problems. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...

Computational problems that are not restricted to yes-or-no answers are called function problems. Examples of function problems include "given an integer n, list the prime factorization of n" and "given two numbers x and y, output x divided by y". In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem... In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. ...