Course contentsShow
← Computer Science
Lesson 1898 of 2,87243. Complexity TheoryFree lesson

Decision Problems and Languages

Define decision problems as yes/no questions and represent them as formal languages for complexity analysis.

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:

  1. Use tools from automata theory and formal languages
  2. Compare problems by their language complexity
  3. Classify problems into complexity classes (P, NP, etc.)
  4. 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.