Decision Problem

computation

Definition

Decision Problem

A decision problem is a tuple where is a set of instances and is the set of yes-instances.

Given an instance , the problem asks whether .

Language

Definition

Language of a Decision Problem

Fix a finite alphabet and a computable encoding . The language of a decision problem with an encoding is

Link to original

Complement

Definition

Co-Decision Problem

A co decision problem of a decision problem is a decision problem that represents the complement (negation) of .

Example: SAT (decision problem) vs UNSAT (co decision problem)

Link to original

Cardinality

Not Every Decision Problem is decidable

A decision problem with a language over a finite alphabet can be identified with a function , where means NO and 1 means YES:

Since is countable, the set of all functions is uncountable. Every algorithm has a finite description and is therefore countable. Hence, there are strictly more decision problems than algorithms, and most decision problems are not decidable.

Link to original