deck_14843125 Flashcards

1
Q

Turing Enumerator

A

Slide 14, lecture 1

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

Acceptance Problem Explanation

A

Slide 19, lecture 1

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

A_TM is undecidable/Diagonalization met bewijs

A

Slide 24, lecture 1

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

complement(A_TM) is T-unrecognizable

A

Slide 25, lecture 1

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

Reducibility method => concept

A

Slide 3, lecture 2

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

Reducibility Method on Halt_TM

A

Slide 2, lecture 2

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

E_TM is undecidable

A

Slide 4, lecture 2

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

Mapping Reducibility concept + proof

A

Slide 5, lecture 2

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

Mapping reduction - properties

A

Slide 6, lecture 2

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

E_TM is T_unrecognizable

A

Slide 9, lecture 2

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

EQ_TM and complement(EQ_TM) are T_unrecognizable

A

Slide 10, lecture 2

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

The Recursion Theorem

A

Slide 15, lecture 2

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

A_TM is undecidable - new proof

A

Slide 16, lecture 2

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

Time Complexity classesdefinition TIME (runs in time?)

A

Slide 7, lecture 3

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

Multi-tape vs 1-tape time

A

Slide 8, lecture 3

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

The Class P

A

Slide 10, lecture 3

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

Path element of P

A

Slide 10, lecture 3

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

Nondeterministic Complexity

A

Slide 12, lecture 3

19
Q

HAMPATH element of NP

A

Slide 13, lecture 3

20
Q

COMPOSITES element of NP

A

Slide 14, lecture 3

21
Q

Intuition for P and NP

A

Slide 15, lecture 3

22
Q

Satisfiability Problem

A

Slide 16, lecture 3

23
Q

Polynomial Time reducibility

A

Slide 17, lecture 3

24
Q

3SAT and CLIQUE

A

Slide 3, lecture 4

25
Q

NP-completeness

A

Slide 6, lecture 4

26
Q

HAMPATH is NP-complete

A

Slide 7, lecture 4

27
Q

Cook-Levin

A

Slide 10, lecture 4

28
Q

SPACE complexity

A

Slide 2, lecture 5

29
Q

Relationship between TIME and SPACE complexity

A

Slide 3, lecture 5

30
Q

NP deelverzameling PSPACE

A

Slide 4, lecture 5

31
Q

TQBF element van PSPACE

A

Slide 5, lecture 5

32
Q

LADDER_DFA element NPSPACELADDER_DFA element PSPACE

A

Slide 8, lecture 5

33
Q

Savitch’s theorem + conclusion

A

Slide 11, lecture 5

34
Q

PSPACE_COMPLETENESS

A

Slide 12, lecture 5

35
Q

TQBF is PSPACE-Complete

A

Slide 14, lecture 5

36
Q

Generalized Geography Game

A

Slide 2, lecture 6

37
Q

GG is PSPACE-complete (TQBF <=p GG)

A

Slide 4, lecture 6

38
Q

Log Space

A

Slide 6, lecture 6

39
Q

Log Space properties: L subset of P

A

Slide 7, lecture 6

40
Q

NL subset of P

A

Slide 8, lecture 6

41
Q

NL_completess

A

Slide 9, lecture 6

42
Q

PATH is NL_Complete

A

Slide 10, lecture 6

43
Q

complement(2SAT) is NL_Complete

A

Slide 11, lecture 6

44
Q

NL = coNL

A

Slide 12, lecture 6