CSCE4115 Final

Question 1

Let A = { | R and S are regular expressions and L(R) ⊆ L(S)}. Show that A is decidable.
Step 1.

Answer 1

X = “On input :

1. Construct DFA E such that L(E) = notL(S) ∩ L(R)

Question 2

Let A = { | R and S are regular expressions and L(R) ⊆ L(S)}. Show that A is decidable.
Step 2.

Answer 2

2. Run TM T on

Question 3

Let A = { | R and S are regular expressions and L(R) ⊆ L(S)}. Show that A is decidable.
Step 3.

Answer 3

3. If T accepts, accept. If T rejects, reject

Question 4

Show that A is Turing-recognizable iff A ≤m ATM.

Step 1

Answer 4

If A <=m Atm then A is Turing recognizable

-Use theorem 5.28

Question 5

Show that A is Turing-recognizable iff A ≤m ATM.

Step 2

Answer 5

If A is Turing recognizable then A<=m Atm

1.Let M∈TM recognizes A [given that A is TM Recognizable]

Question 6

Show that A is Turing-recognizable iff A ≤m ATM.

Step 3

Answer 6

Atm = { | M∈TM ∧ M~w}

Question 7

Show that A is Turing-recognizable iff A ≤m ATM.

Step 4

Answer 7

Therefore x ∈ A <=> ∈ Atm is a mapping reduction from A to Atm

Question 8

Is the following formula satisfiable? (𝑥 ∨ 𝑦) ∧ (𝑥 ∨ not𝑦) ∧ (not𝑥 ∨ 𝑦) ∧ (not𝑥 ∨ not𝑦)

Answer 8

(x,y) may have only 4 values, (0,0), (0,1), (1,0), and (1,1) None satisfy the formula the formula is not satisfiable

Question 9

Show that P is closed under union and NP is closed under union.
paragraph

Answer 9

P is closed under union.
For any two P languages, L1 and L2.
Let M1 and M2 be the TMs that decide them in polynomial time.
We construct a TM, m’, that decides L1 U L2 in polynomial time

Question 10

Show that P is closed under union and NP is closed under union.
Step 1

Answer 10

M’ = “On input :

1. Run M1 on w. if it accepts, accept

Question 11

Show that P is closed under union and NP is closed under union.
Step 2

Answer 11

2. Run M2 on w. if it accepts, accept.

if it rejects, reject

Question 12

DOMINATING-SET = { | has a dominating set with k vertices}.
Show that it is NP-complete by giving a reduction from VERTEX-COVER.
Step 1

Answer 12

VC <=pDS

Let G= (V,E) be a connected graph. Construct G’=(V’E’) by creating for each e∈G one new vertex and two new edges

Question 13

Show that it is NP-complete by giving a reduction from VERTEX-COVER.
Step 1.a

Answer 13

We must show that if G has a vertex cover of size K then G’ has a dominating set a size K and viceversa

Question 14

Show that it is NP-complete by giving a reduction from VERTEX-COVER.
Step 2

Answer 14

D -> S
Let D subset V
Let (u,v) ∈ E be any edge in E
Either u or v or both must be a number of D
Thus (u,v) touches a member of D and S = D is a vertex cover of G

Question 15

Show that it is NP-complete by giving a reduction from VERTEX-COVER.
Step 3

Answer 15

S -> D

Every triangle of G’ has at least one vertex in S. Thus D = S is a dominating set of G’

Question 16

2n = O(n)

Answer 16

true

c = 2

Question 17

n^2 = O(n)

Answer 17

false

Question 18

n^2 = O(n ln^2 n)

Answer 18

false

1/(2/n) = infiniti

Question 19

n ln n = O(n^2)

Answer 19

false

1/n = 0

Question 20

Prove 3SAT is NPC

Step 1.

Answer 20

Choose SAT and show SAT <=p 3SAT

Question 21

Prove 3SAT is NPC

Step 2.

Answer 21

3SAT ∈ NP

Given a potential 3Sat solution, one literal in each clause must be true. This is in polynomial time

Question 22

Prove 3SAT is NPC

Step 3.

Answer 22

SAT <=p 3SAT
Input phi and restrict phi to phi ∈ CNF
In genral a clause a1 V a2 V … V ak is transformed to yeild k-2 clauses in trident(phi) with k-3 link variables fish,B,… this is in polynomial time

Question 23

Prove 3SAT in NPC

Step 4.

Answer 23

phi trident
Any assignment of value to clause C causing C to be true (or false) can be extended to cause Dc to be true(or false)
f^-1(trident) is not satisfiable only if phi is not satisfiable