patternModerate
Why are decision problems commonly used in complexity theory?
Viewed 0 times
whyareusedtheorydecisionproblemscomplexitycommonly
Problem
From Wikipedia:
The type of computational problem: The most commonly used problems are
decision problems. However, complexity classes can be defined based on
function problems, counting problems, optimization problems, promise
problems, etc.
I also saw the definitions of NP-complete, NP-hard, NP, ..., are defined for decision problems only. I wonder why that is the case?
Is it because any other problem can be equivalently converted to a decision problem?
The type of computational problem: The most commonly used problems are
decision problems. However, complexity classes can be defined based on
function problems, counting problems, optimization problems, promise
problems, etc.
I also saw the definitions of NP-complete, NP-hard, NP, ..., are defined for decision problems only. I wonder why that is the case?
Is it because any other problem can be equivalently converted to a decision problem?
Solution
Oftentimes decision problems are used because they allow a precise and simple definition of the problem and, as stated, many other problems can be converted to an equivalent decision problem.
Other types of problems are also considered in complexity theory, for instance Function Problems and Search Problems.
Other types of problems are also considered in complexity theory, for instance Function Problems and Search Problems.
Context
StackExchange Computer Science Q#4874, answer score: 11
Revisions (0)
No revisions yet.