Problems
- Computational problem
- Optimization problem
- Decision problem In this course, we will look at decision problems.
Decision problems - why choose them?
- Easy to define
- Interesting and strong conclusions from the solution
- Computational problems can be represented as a decision one (or series of them)
Decision problem
Input representation
Input is usually represented as a sequence of elements of some alphabet
Alphabet definition
A finite (in this course) set of all characters(“letters”) necessary to represent the input
Actions of alphabet definition
- Concatenation -
- Power -
Word definition
A sequence of letters from the given alphabet. Not every word is a valid input.
Actions on words definition
- Concatenation - denoted
or just - Power - denoted
. Note that
Language definition
A set of words, not necessarily finite(!)
Actions on languages
- All actions on sets
- Concatenation -
- Power -
. Note that - Kleene closure -
and
Reverse definition
Prefix, suffix and sub definition
Defining decision problem via language
Any decision problem can be defined as a language definition
Is this representation unique? - No! For example: