ToC Flashcards by mohammed shabot

Q

Turing Enumerator

A

Slide 14, lecture 1

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Acceptance Problem Explanation

A

Slide 19, lecture 1

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

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

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

Q

Reducibility method => concept

A

Slide 3, lecture 2

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

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

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

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

Q

Mapping reduction - properties

A

Slide 6, lecture 2

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

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

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

Q

The Recursion Theorem

A

Slide 15, lecture 2

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

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

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

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

Q

The Class P

A

Slide 10, lecture 3

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

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

Q

Nondeterministic Complexity

A

Slide 12, lecture 3

Q

HAMPATH element of NP

A

Slide 13, lecture 3

Q

COMPOSITES element of NP

A

Slide 14, lecture 3

Q

Intuition for P and NP

A

Slide 15, lecture 3

Q

Satisfiability Problem

A

Slide 16, lecture 3

Q

Polynomial Time reducibility

A

Slide 17, lecture 3

Q

3SAT and CLIQUE

A

Slide 3, lecture 4

NP-completeness

Slide 6, lecture 4

HAMPATH is NP-complete

Slide 7, lecture 4

Cook-Levin

Slide 10, lecture 4

SPACE complexity

Slide 2, lecture 5

Relationship between TIME and SPACE complexity

Slide 3, lecture 5

NP deelverzameling PSPACE

Slide 4, lecture 5

TQBF element van PSPACE

Slide 5, lecture 5

LADDER_DFA element NPSPACELADDER_DFA element PSPACE

Slide 8, lecture 5

Savitch's theorem + conclusion

Slide 11, lecture 5

PSPACE_COMPLETENESS

Slide 12, lecture 5

TQBF is PSPACE-Complete

Slide 14, lecture 5

Generalized Geography Game

Slide 2, lecture 6

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

Slide 4, lecture 6

Log Space

Slide 6, lecture 6

Log Space properties: L element of P

Slide 7, lecture 6

NL element of P

Slide 8, lecture 6

NL_completess

Slide 9, lecture 6

PATH is NL_Complete

Slide 10, lecture 6

complement(2SAT) is NL_Complete

Slide 11, lecture 6

NL = coNL

Slide 12, lecture 6