Lesson plan
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.…
Article summary
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.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.