Flashcards in CSCE4115 Final Deck (23):

1

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

Step 1.

###
X = "On input :

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

2

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

Step 2.

### 2. Run TM T on

3

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

Step 3.

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

4

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

Step 1

###
If A <=m Atm then A is Turing recognizable

-Use theorem 5.28

5

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

Step 2

###
If A is Turing recognizable then A<=m Atm

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

6

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

Step 3

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

7

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

Step 4

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

8

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

### (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

9

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

paragraph

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

10

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

Step 1

###
M' = "On input :

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

11

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

Step 2

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

if it rejects, reject

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

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

13

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

Step 1.a

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

14

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

Step 2

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

15

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

Step 3

###
S -> D

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

16

## 2n = O(n)

###
true

c = 2

17

## n^2 = O(n)

### false

18

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

###
false

1/(2/n) = infiniti

19

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

###
false

1/n = 0

20

##
Prove 3SAT is NPC

Step 1.

### Choose SAT and show SAT <=p 3SAT

21

##
Prove 3SAT is NPC

Step 2.

###
3SAT ∈ NP

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

22

##
Prove 3SAT is NPC

Step 3.

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

23