Table of Contents

• Purpose
• Intuitive Definition
• Formal Definition
• Decision Problems
• Decision Problems and Language Recognition Problems

• Purpose of this unit

  • The fundamental issue we will focus on for the remainder of this course are problems and problem solving.

  • The purpose of this unit is to provide you with both an informal and formal understanding of what problems are.

  • That is, this unit answer the question:

    • What is a problem in computer science?

  • Four other questions to keep in mind and which we will address a bit later are

    • How do we solve problems in computer science?
      • Stated another way, what is an algorithm?
    • Are there problems which cannot be solved?
    • Is there a general purpose algorithm which can execute any algorithm?
    • Is there a difference between "algorithms" and "data"?

• Intuitive Definition of Problems

  • Distinguishing between two meanings of the word problem

    • In English, there are two main definitions for the word problem

      1. A problem can be a difficulty or hindrance.
         Something is a problem if it hinders you from doing something or makes doing something more difficult.

         • The problem with creating this report is I do not have the data from last year.

      2. A problem can be a task or something to be done.

         1. Add the numbers 37 and 45.
         2. Add the numbers 15 and 74.
         3. Sort the list of students in this class by last name.
         4. Sort the list of students in this class by PID.

    • In computer science, we will focus on the second definition of a problem being a task.

  • The intuitive definition of a problem is that a problem is a set, usually infinite, of related tasks.

  • Example Problems

    • The two distinct tasks

      • Add the numbers 37 and 45.
      • Add the numbers 15 and 74.

    • The two distinct tasks

      • Sort the list of students in this class by last name.
      • Sort the list of students in this class by PID.

    • The ADDITION Problem

      • Add any two numbers

    • The INCREMENT Problem

      • Add 1 to any number.

    • The TERNARY ADDITION Problem

      • Add any three numbers

    • The SORTING Problem

      • sort any list of names.

• Formal Definition of Problems

  • Tasks and Input Instances

    • Notice in our list of example problems that each of the "tasks" in the set are identical.

    • The real difference between the tasks is that the items to be acted upon may take different values.

    • Example

      • In the addition problem, the only difference is the numbers to be added, but the fundamental task of addition is common to all the tasks that need to be accomplished.

    • We call each collection of items to be acted upon an input instance.

  • Definition

    • A problem is characterized by

      1. A set of input instances

         • This set is usually described in the "generic input instance" fashion

      2. A task to be performed on the input instances

  • Examples

    1. The addition problem

       • A generic input instance

         • Two positive integers x and y

       • The task

         • Add the numbers x and y

    2. The sorting problem

       • A generic input instance

         • A list of numbers x₁ through x_n for some integer n > 0.

       • The task

         • Output the list of numbers x₁ through x_n in nondecreasing order.

    3. Recognizing the language L={aⁿbⁿ | n > 0}

       • A generic input instance

         • A finite string x over the alphabet {a,b}

       • The task

         • Answer the question "Is x in L?"

• Decision Problems

  • Problems where the task is to answer a Yes/No question are called Decision Problems.

    • The language recognition problem is a decision problem, but the sorting problem and the addition problem are not decision problems.

  • In general, other problems can be solved by a series of decision problems.

    • Consider the following example which shows how the addition problem can be essentially solved by solving a series of decision problems.

      1. Take the 2 inputs x and y for the addition problem.

      2. Initialize z = 1.

      3. Ask if x + y = z.

      4. If answer is yes, then output z, otherwise increment z and return to step 3.

    • How would you frame step 3 as a decision problem clearly specifying what a generic input instance looks like and the task?

  • As a result, we will focus our attention on decision problems.

• Translating A Decision Problem to Language Recognition Problem

  • We can view a decision problem as a set membership question.

    • Let INPUT be the set of all possible input instances.

    • Let YES be the set of input instances for which the answer is YES.

    • A decision problem is essentially asking if an input instance $I$ belongs to YES.

  • All input instances can be encoded as strings over a finite alphabet such as {a,b}, {0,1}, or the English alphabet.

  • Example

    • Consider the decision version of the addition problem.

    • Let b(x) be the number x in binary notation.

    • Let b(y) be the number y in binary notation.

    • Let b(z) be the number z in binary notation.

    • We encode the input instance x, y, and z as b(x);b(y);b(z) using the input alphabet {0,1,;}.
      • 1001;101;1111 is the encoding of the input instance x = 9, y = 5, and z = 15.

  • We can view any decision problem as a language recognition problem.

    • The set of input instances consists of all finite strings over the input alphabet.

    • Note the input instances will be divided into three types of strings:

      • strings which encode yes input instances such as 1001;101;1110

      • strings which encode no input instances such as 1001;101;1111

      • strings which do not encode legal input instances to the original decision problem such as ;;;110;

    • It is easy to decide if a string belongs to this third class of strings in general.

    • Thus, the basic question reduces to determining if a string which is a legal encoding of an input instance belongs to the set of yes instances or the set of no instances.

  • Thus, this general framework of the language recognition problem actually presents a framework for studying which problems can be solved by computers.