Computational problem
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." 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.
- Comment
- enIn 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." 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.
- Has abstract
- enIn 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." 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 class P for classical 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}*. For example, numbers can be represented as binary strings using binary encoding.
- Hypernym
- Object
- Is primary topic of
- Computational problem
- Label
- enComputational problem
- Link from a Wikipage to another Wikipage
- Abstract machine
- Algorithm
- Analysis of algorithms
- BQP
- Cambridge University Press
- Category:Computational problems
- Category:Theoretical computer science
- Combinatorial optimization
- Complexity class
- Computational complexity
- Computational complexity theory
- Counting problem (complexity)
- Decision problem
- Factoring problem
- Function problem
- Hardness of approximation
- Independent set (graph theory)
- Interactive proof system
- Lateral computing
- Maximum independent set problem
- Model of computation
- NP-hard
- Operations research
- Optimization problem
- P (complexity)
- Primality testing
- Promise problem
- Property testing
- Regular expression
- Relation (mathematics)
- Search problem
- Set (mathematics)
- String (computer science)
- Theoretical computer science
- The Princeton Companion to Mathematics
- Total function
- Transcomputational problem
- Travelling salesman problem
- Undecidable problem
- SameAs
- 3A6Kp
- Computational problem
- m.0cbp56
- Problema computacional
- Problema computacional
- Problema computazionale
- Problème algorithmique
- Problem obliczeniowy
- Q3435924
- Računski problem
- Számítási probléma
- Υπολογιστικό πρόβλημα
- Рачунски задатак
- مسئله رایانشی
- प्रॉब्लम (कंप्यूटर विज्ञान)
- Subject
- Category:Computational problems
- Category:Theoretical computer science
- WasDerivedFrom
- Computational problem?oldid=1099779198&ns=0
- WikiPageLength
- 7201
- Wikipage page ID
- 4594672
- Wikipage revision ID
- 1099779198
- WikiPageUsesTemplate
- Template:Citation
- Template:Efn
- Template:Main
- Template:No footnotes
- Template:Notelist
- Template:Short description