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 one 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.
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?".
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.
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".
Theoretical computer science is the collection of topics of computer science that focuses on the more abstract, logical and mathematical aspects of computing, such as the theory of computation, analysis of algorithms and semantics of programming languages.
..... Click the link for more information.
Mathematics (colloquially, maths or math) is the body of knowledge centered on such concepts as quantity, structure, space, and change, and also the academic discipline that studies them. Benjamin Peirce called it "the science that draws necessary conclusions".
..... Click the link for more information.
computer is a machine which manipulates data according to a list of instructions.
Computers take numerous physical forms. The first devices that resemble modern computers date to the mid-20th century (around 1940 - 1941), although the computer concept and various machines
..... Click the link for more information.
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
Instantiation may be
- *A concept in Platonism, see idea
- *Instantiation principle - the idea that if properties exist, the essence that "has" the properties must necessarily exist
- *
..... Click the link for more information. In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
The simplest computational resources are computation time, the number of steps necessary to solve a problem, and
..... Click the link for more information.
computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation.
Computability theory differs from the related discipline of computational complexity theory, which deals with the
..... Click the link for more information.
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem.
..... Click the link for more information.
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.
..... Click the link for more information.
integer factorization is the process of breaking down a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer.
..... Click the link for more information.