Scribd
Upload
26 views4 pages

Examples of Computational Problems

A computational problem in theoretical computer science involves finding solutions through algorithms, with examples including factoring and the Halting problem. Problems can be categorized into types such as decision problems, search problems, counting problems, optimization problems, function problems, and promise problems, each with distinct characteristics and representations. The field of computational complexity theory studies the efficiency and resource requirements of algorithms for these problems.

Uploaded by

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

Examples of Computational Problems

A computational problem in theoretical computer science involves finding solutions through algorithms, with examples including factoring and the Halting problem. Problems can be categorized into types such as decision problems, search problems, counting problems, optimization problems, function problems, and promise problems, each with distinct characteristics and representations. The field of computational complexity theory studies the efficiency and resource requirements of algorithms for these problems.

Uploaded by

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

Computational problem

In theoretical computer science, a problem is one that asks for a solution in terms of an algorithm. For
example, the problem of factoring

"Given a positive integer n, find a nontrivial prime factor of n."

is a computational problem that has a solution, as there are many known integer factorization algorithms.
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. The question then is, whether there exists an algorithm that maps
instances to solutions. For example, in the factoring problem, the instances are the integers n, and
solutions are prime numbers p that are the nontrivial prime factors of n. An example of a computational
problem without a solution is the Halting problem. Computational problems are one of the main objects
of study in theoretical computer science.

One is often interested not only in mere existence of an algorithm, but also how efficient the algorithm
can be. The field of computational complexity theory addresses such questions by determining the
amount of resources (computational complexity) solving a given problem will require, and explain why
some problems are intractable or undecidable. Solvable 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 classes

P, problems that consume polynomial time for deterministic classical machines


BPP, problems that consume polynomial time for probabilistic classical machines (e.g.
computers with random number generators)
BQP, problems that consume polynomial time for probabilistic quantum machines.
Both instances and solutions are represented by binary strings, namely elements of {0, 1}*.[a] For
example, natural numbers are usually represented as binary strings using binary encoding. This is
important since the complexity is expressed as a function of the length of the input representation.

Types

Decision problem
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, ...}


Search problem
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 prime factor of n.

Counting problem
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) }|.

Optimization problem
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 are represented by their objective function and their constraints.

Function problem
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.
Promise problem
In computational complexity theory, it is usually implicitly assumed that any string in {0, 1}* represents
an instance of the computational problem in question. However, sometimes not all strings {0, 1}*
represent valid instances, and one specifies a proper subset of {0, 1}* as the set of "valid instances".
Computational problems of this type are called promise problems.

The following is an example of a (decision) promise problem:

"Given a graph G, determine if every independent set in G has size at most 5, or G has an
independent set of size at least 10."

Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at
least 10.

Decision promise problems are usually represented as pairs of disjoint subsets (Lyes, Lno) of {0, 1}*. The
valid instances are those in Lyes ∪ Lno. Lyes and Lno represent the instances whose answer is yes and no,
respectively.

Promise problems play an important role in several areas of computational complexity, including
hardness of approximation, property testing, and interactive proof systems.

See also
Lateral computing, alternative approaches to solving problems computationally
Model of computation
Transcomputational problem

Notes
a. See regular expressions for the notation used

References
Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984), "The complexity of promise problems
with applications to public-key cryptography", Information and Control, 61 (2): 159–173,
doi:10.1016/S0019-9958(84)80056-X ([Link]
056-X).
Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge
University Press, ISBN 978-0-521-88473-0.
Goldreich, Oded; Wigderson, Avi (2008), "IV.20 Computational Complexity", in Gowers,
Timothy; Barrow-Green, June; Leader, Imre (eds.), The Princeton Companion to
Mathematics, Princeton University Press, pp. 575–604, ISBN 978-0-691-11880-2.

Retrieved from "[Link]

Common questions

Powered by AI

A promise problem in complexity theory is a type of computational problem where not all inputs are valid; only certain 'promised' inputs are considered. It is represented by two disjoint subsets of valid instances with known outcomes ('yes' or 'no'). Promise problems are significant for their utility in areas like hardness of approximation and interactive proof systems, where they test the boundaries of problem-solving under restricted conditions .

In computational complexity, binary strings serve as universal representations for both instances and solution spaces in computational problems. This representation is critical as it defines the input length, which is a key factor in assessing the problem's complexity. Complexity measures like time and space are often expressed as functions of this input length .

In decision problems, representing instances that yield a 'yes' answer as sets simplifies computational analysis by focusing on solutions meeting the decision criterion. This representation forms the basis for determining membership in complexity classes and helps in applying theoretical frameworks to study algorithmic efficiency and feasibility for these problems .

Optimization problems are vital in operations research as they involve finding the most efficient solutions within a set of constraints, critical for resource allocation and decision making. In complexity theory, these problems are often NP-hard, exemplifying resource-intensive tasks. Complexity analysis guides the development of approximate methods where exact solutions are computationally infeasible .

BPP and BQP address probabilistic and quantum computational paradigms, thus extending classical computability by allowing problems potentially unsolvable by deterministic machines to be efficiently addressed. BPP uses randomness, and BQP leverages quantum mechanics, indicating broader computational capabilities. These classes highlight potential power benefits of new computational models and inspire research into quantum computing and probabilistic algorithms .

A decision problem in computational complexity asks for a 'yes' or 'no' answer to a given computation problem for each instance, such as determining if a number is prime. In contrast, a search problem involves finding an arbitrary string as a solution, such as identifying prime factors of a given integer .

Complexity classes categorize problems based on the resources needed to solve them, often focusing on time and space. For example, class P consists of problems solvable in polynomial time by deterministic machines. This classification helps determine which problems are efficiently computable, guides the development of algorithms, and sets thresholds for designing computational systems. Problems not efficiently solvable, such as those in NP-hard or undecidable classes, signify limitations in problem-solving capabilities .

Counting problems differ from search problems as they seek to determine the number of valid solutions rather than finding the solutions themselves. They offer insight into the complexity and richness of problem instances by quantifying possibilities, often helping to assess problem difficulty and informing resource allocation for computational solutions .

Undecidable problems, like the Halting problem, are those for which no algorithm can provide a definitive solution for all instances. These problems demonstrate limits to computation, indicating inherent theoretical boundaries where algorithmic logic cannot resolve certain problem types. The existence of such problems invites exploration into alternative computation models and helps in understanding the hierarchy and limitations of computational resources .

Search relations in search problems define the connection between instances and solutions, representing possible pairs as a relation. This helps in understanding problem domains by clearly laying out the input-output mappings that must be achieved, facilitating the analysis of problem complexity and aiding the design of effective algorithms .

You might also like