Discrete Mathematics

-------------------------------------------------------------AUTOMATA

2n

• the subset B

\:A

of

"yes" instances.

For

example, to decide

if

a given graph is connected, the set

of

possible inputs is the set

of

all

(encodings of) graphs, and the

"yes"

instances are the connected graphs.

To

decide

if

a given number is a

prime, the set

of

possible inputs is the set

of

all (binary encodings of) integers, and the "yes" instances are the

primes.

In this chapter we will mostly consider decision problems as opposed to functions with more general

outputs.

We

do

this for mathematical simplicity, and because the behavior

we

want to study is already present ...