Exam

Question 1

decidability

Answer 1

language is decidable if some Turing machine decides it

Question 2

decidability proof

Answer 2

A = { < C > | C is machine M }
Turing machine M = “On input :
1. construct two DFA’s/CFG’s/PDA’s one recognizing the language to prove and the other recognizing the complement of the language to prove
2. construct DFA/CFG/PDA with L(A) = intersection of two language of 1.
3. test whether L(A) = emptiest using E_(DFA/CFG/PDA)
decider T from theorem of the book
4. if T accepts, reject; if T rejects, accept

Question 3

if A is undecidable and reducible to B then …

Answer 3

B is undecidable

Question 4

decidability of an NFA or regex

Answer 4

REG to NFA to DFA

Question 5

recognizability

Answer 5

a language is TM-recognizable if some Turing machine recognizes it

Question 6

all decidable languages are …

Answer 6

recognizable

Question 7

proof L is not TM-recognizable

Answer 7

it suffices to show that non-recognizable languages such as complement A_TM or E_TM is mapping reducible to L

Question 8

co-recognizable

Answer 8

L is co-recognizable if complement L is recognizable

Question 9

P

Answer 9

U_k TIME (n^k)
class of languages that are decidable in polynomial time on deterministic single tape TM

Question 10

proof L in P

Answer 10

Given algorithm A
A = "On input <i>
1. 
2.
3. ..., accept; ..., reject"

Show A runs in polynomial time</i>

Question 11

NP

Answer 11

class of languages that have polynomial time verifiers
a language is in NP iff it is decided by some nondeterministic polynomial time Turing machine

Question 12

verifier

Answer 12

a verifier for language A is an algorithm V, where
A = {w | V accepts < w, c > for some string c}
c = certificate

Question 13

proof L in NP

Answer 13

V = "On input <<>, >:
1. test whether ..., reject
2. test whether ..., reject
3. otherwise accept
"
prove in polynomial time

Question 14

coNP

Answer 14

contains languages that are complements of languages in NP
proof: show complement is in NP

example: { | phi is contradictory Boolean formula}

Question 15

NP-hard

Answer 15

language is NP-hard if all problems in NP are polynomial time reducible to it

Question 16

proof L is NP-hard

Answer 16

1. choose known NP-hard language L’
2. prove L’ < _ p L
   a. give polynomial time reduction f from L’ to L
   b. prove f is reduction so w in L’ iff f(w) in L
   c. prove f i s computable in polynomial time

Question 17

co NP-hard

Answer 17

contains language that are complements of language in NP-hard

Question 18

NP-complete

Answer 18

is a problem for which the correctness of each solution can be quickly verified and a brute-force searching algorithm can actually find a solution by trying all possible solutions

Question 19

proof L in NP-complete

Answer 19

1. prove L is in NP

2. prove L is NP-hard

Question 20

reducibility

Answer 20

if A reduces to B we can use B to solve A

Question 21

computable function

Answer 21

a function f is computable if some TM M, on every input w, halts with just f(w) on its tape

Question 22

mapping reducibility

Answer 22

language A is mapping reducible to B, A < _ m B, if there is a computable function f for every w such that
w in A < = > f(w) in B

f is reduction from A to B

Question 23

if A

Answer 23

complement A

Question 24

set 1

Answer 24

1. regular languages
2. languages recognizable by NFA
3. languages recognizable by DFA

Question 25

set 2

Answer 25

1. context-free languages | 2. languages recognizable by nondeterministic PDA

Question 26

set 3

Answer 26

1. P

Question 27

set 4

Answer 27

1. NP | 2. languages decidable by nondeterministic Turing machines in polynomial time

Question 28

set 5

Answer 28

1. PSPACE

Question 29

set 6

Answer 29

1. languages decidable by 1-tape Turing machines 2. languages decidable by multitape Turing machines 3. languages decidable by nondeterministic Turing machines

Question 30

set 7

Answer 30

1. languages recognizable by 1-tape Turing machines

Question 31

set comparison

Answer 31

1 -/ 2 -/ 3 - 4 - 5 -/ 6 -/ 7

Question 32

big-O

Answer 32

f, g: N -> R^+. f(n) = O(g(n)) when c, m in N such that for every n >_ m: f(n) < _ c g(n)

Question 33

small-o

Answer 33

f,g: N -> R^+ f(n) = o(g(n)) when c,m in N such that for every n >_ m: f (n) < c g(n)

Question 34

language is decidable iff ...

Answer 34

it is recognizable and co-recognizable

Question 35

if A < _ m B and B is recognizable then ...

Answer 35

then A is recognizable

Question 36

if A < _ m B and A is undecidable then ...

Answer 36

then B is undecidable

Question 37

if A < _ m B and B is decidable then ...

Answer 37

then A is decidable

Question 38

if A < _ m B and A is unrecognizable

Answer 38

then B is unrecognizable

Question 39

let t(n) be a function where t(n) >_ n ...

Answer 39

1. then every t(n) time multitape TM has an equivalent O(t^2(n)) time single tape TM 2. then every t(n) time non deterministic single-tape TM has an equivalent 2^(O(t(n))) time deterministic single-tape TM

Question 40

SAT in P iff ...

Answer 40

P = NP

Question 41

if A < _ p B and B in P then ...

Answer 41

A in P

Question 42

if B is NP-complete and B in P then ...

Answer 42

P = NP

Question 43

if B is NP-complete and B < _ p C for C in NP then ...

Answer 43

C is NP-complete

Question 44

(3)SAT is ...

Answer 44

NP-complete

Question 45

Rice's theorem

Answer 45

for every nontrivial property P of TM-recognizable language, the following language is undecidable: L_P = {< M > | M is TM and L(M) has property P}

Question 46

Cobham-Edmonds thesis

Answer 46

a computational problem can be "feasibly computed" by a machine iff it can be solved in polynomial time

Question 47

A_m = ...

Answer 47

{< B , w > | B is m accepting w}

Question 48

E_m = ...

Answer 48

{< B > | B is m and L(B) = emptyset}

Question 49

EQ_M = ...

Answer 49

{< B , C > | B, C is m and L(B) = L(C)}

Question 50

decidable languages

Answer 50

``` A_DFA A_NFA A_PDA A_REX A_CFG E_DFA E_PDA E_CFG EQ_DFA ```

Question 51

undecidable languages

Answer 51

``` A_TM E_TM EQ_CFG EQ_TM HALT_TM ```

Question 52

recognizable languages

Answer 52

A_TM | HALT_TM

Question 53

unrecognizable languages

Answer 53

E_TM - -A_TM - -HALT_TM