CSCE4115 Final Flashcards Preview

Programming > CSCE4115 Final > Flashcards

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

Prove 3SAT in NPC
Step 4.

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