# Computational problem

## Problem a computer might be able to solve / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Computational problem?

Summarize this article for a 10 year old

In theoretical computer science, a **computational problem** is a problem that may be solved by an algorithm. For example, the problem of **factoring**

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

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (October 2015) |

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 are the 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 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}^{*}.^{[lower-alpha 1]} 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.