Decision Problems and Languages
What You'll Learn
You'll learn how to represent computational problems as yes/no questions and formal languages—the foundation for analyzing complexity.
The Core Idea
In complexity theory, we need a standardized way to talk about problems. A decision problem is any question that has exactly two possible answers: "yes" or "no." Think of it like a light switch—it's either on or off, with no in-between.
For example:
- "Is this number prime?" (yes/no)
- "Does this graph contain a cycle?" (yes/no)
- "Is this string a palindrome?" (yes/no)
But how do we represent these problems formally? We use languages!
From Problems to Languages
Here's the key insight: every decision problem can be represented as a formal language—a set of strings over some alphabet.
For a decision problem, we define:
- The language L = all input strings for which the answer is "yes"
- Strings in the language → answer is "yes"
- Strings not in the language → answer is "no"
Example: Palindromes
Consider the decision problem: "Is string x a palindrome?"
We represent this as the language:
L_palindrome = {x | x = x^reverse}
So "racecar" ∈ L_palindrome (yes), but "hello" ∉ L_palindrome (no).
Why This Matters
This representation lets us:
- Use tools from automata theory and formal languages
- Compare problems by their language complexity
- Classify problems into complexity classes (P, NP, etc.)
- Apply techniques like reductions between languages
Instead of asking "How hard is this problem?" we now ask "What complexity class does this language belong to?"
Key Takeaway: Decision problems are yes/no questions that can be formally represented as languages, where membership in the language means "yes"—this encoding enables rigorous complexity analysis.