[go: up one dir, main page]
Scribd
Upload
84 views2 pages

Computational Problem

The document discusses different types of computational problems including decision problems, search problems, counting problems, optimization problems, and function problems. It provides examples like factoring, primality testing, and the traveling salesman problem. Computational complexity theory studies the resources required to solve computational problems.

Uploaded by

Balakrishnan.G
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
84 views2 pages

Computational Problem

The document discusses different types of computational problems including decision problems, search problems, counting problems, optimization problems, and function problems. It provides examples like factoring, primality testing, and the traveling salesman problem. Computational complexity theory studies the resources required to solve computational problems.

Uploaded by

Balakrishnan.G
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Computational problem

In theoretical computer science, a computational problem is a problem that a computer might be able
to solve or a question that a computer may be able to answer. 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 describe 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 class P for cassical machines, and BQP for quantum machines.

It is typical of many problems to represent both instances and solutions by binary strings, namely
elements of {0, 1}*.[a] For example, numbers can be represented as binary strings using binary
encoding.

Types

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 = {2, 3, 5, 7, 11, ...}


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 = {(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 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 {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) }|.

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 traveling 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.

You might also like