- 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"?

- How do we solve problems in computer science?

#### Intuitive Definition of Problems

- Distinguishing between two meanings of the word
*problem*- In English, there are two main definitions for the word
*problem*- 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.

- A problem can be a task or something to be done.
- Add the numbers 37 and 45.
- Add the numbers 15 and 74.
- Sort the list of students in this class by last name.
- Sort the list of students in this class by PID.

- A problem can be a difficulty or hindrance.
- In computer science, we will focus on the second definition of a problem being a task.

- In English, there are two main definitions for the word
- 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.

- The two distinct tasks

- Distinguishing between two meanings of the word
#### 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
- A set of input instances
- This set is usually described in the "generic input instance" fashion

- A task to be performed on the input instances

- A set of input instances

- A problem is characterized by
- Examples
- The addition problem
- A generic input instance
- Two positive integers
*x*and*y*

- Two positive integers
- The task
- Add the numbers
*x*and*y*

- Add the numbers

- A generic input instance
- The sorting problem
- A generic input instance
- A list of numbers
*x*through_{1}*x*for some integer_{n}*n*> 0.

- A list of numbers
- The task
- Output the list of numbers
*x*through_{1}*x*in nondecreasing order._{n}

- Output the list of numbers

- A generic input instance
- Recognizing the language
*L={a*^{n}b^{n}| n > 0}- A generic input instance
- A finite string
*x*over the alphabet*{a,b}*

- A finite string
- The task
- Answer the question "Is
*x*in*L*?"

- Answer the question "Is

- A generic input instance

- The addition problem

- Tasks and Input Instances
#### 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.
- Take the 2 inputs
*x*and*y*for the addition problem. - Initialize
*z = 1*. - Ask if
*x + y = z*. - If answer is yes, then output
*z*, otherwise increment*z*and return to step 3.

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

- Consider the following example which shows how the
addition problem can be essentially solved by solving a
series of decision problems.
- As a result, we will focus our attention on decision problems.

- Problems where the task is to answer a Yes/No question
are called
#### 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*.

- 1001;101;1111 is the encoding of the input instance

- 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.

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