Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Logical complexity > Exam > Flashcards

Exam Flashcards

1
Q

decidability

A

language is decidable if some Turing machine decides it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

decidability proof

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

if A is undecidable and reducible to B then …

A

B is undecidable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

decidability of an NFA or regex

A

REG to NFA to DFA

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

recognizability

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

all decidable languages are …

A

recognizable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

proof L is not TM-recognizable

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

co-recognizable

A

L is co-recognizable if complement L is recognizable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

P

A 
U_k TIME (n^k)
class of languages that are decidable in polynomial time on deterministic single tape TM
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

proof L in P

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

Show A runs in polynomial time</i>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

NP

A 
class of languages that have polynomial time verifiers
a language is in NP iff it is decided by some nondeterministic polynomial time Turing machine
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

verifier

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

proof L in NP

A 
V = "On input <<>, >:
1. test whether ..., reject
2. test whether ..., reject
3. otherwise accept
"
prove in polynomial time
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

coNP

A

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

example: { | phi is contradictory Boolean formula}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

NP-hard

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

proof L is NP-hard

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

co NP-hard

A

contains language that are complements of language in NP-hard

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

NP-complete

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

proof L in NP-complete

A
  1. prove L is in NP

2. prove L is NP-hard

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

reducibility

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

computable function

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

mapping reducibility

A

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

23
Q

if A

A

complement A

24
Q

set 1

A
  1. regular languages
  2. languages recognizable by NFA
  3. languages recognizable by DFA
25
Q

set 2

A
  1. context-free languages

2. languages recognizable by nondeterministic PDA

26
Q

set 3

A
  1. P
27
Q

set 4

A
  1. NP

2. languages decidable by nondeterministic Turing machines in polynomial time

28
Q

set 5

A
  1. PSPACE
29
Q

set 6

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

set 7

A
  1. languages recognizable by 1-tape Turing machines
31
Q

set comparison

A

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

32
Q

big-O

A

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)

33
Q

small-o

A

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)

34
Q

language is decidable iff …

A

it is recognizable and co-recognizable

35
Q

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

A

then A is recognizable

36
Q

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

A

then B is undecidable

37
Q

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

A

then A is decidable

38
Q

if A < _ m B and A is unrecognizable

A

then B is unrecognizable

39
Q

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

A
  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
40
Q

SAT in P iff …

A

P = NP

41
Q

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

A

A in P

42
Q

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

A

P = NP

43
Q

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

A

C is NP-complete

44
Q

(3)SAT is …

A

NP-complete

45
Q

Rice’s theorem

A

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}

46
Q

Cobham-Edmonds thesis

A

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

47
Q

A_m = …

A

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

48
Q

E_m = …

A

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

49
Q

EQ_M = …

A

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

50
Q

decidable languages

A 
A_DFA
A_NFA
A_PDA
A_REX
A_CFG
E_DFA
E_PDA
E_CFG
EQ_DFA
51
Q

undecidable languages

A 
A_TM
E_TM
EQ_CFG
EQ_TM
HALT_TM
52
Q

recognizable languages

A

A_TM

HALT_TM

53
Q

unrecognizable languages

A

E_TM

  • -A_TM
  • -HALT_TM

Logical complexity (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions