deck_14843125 Flashcards by cas symens | Brainscape

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

Q

NP-completeness

A

Slide 6, lecture 4

Q

HAMPATH is NP-complete

A

Slide 7, lecture 4

Q

Cook-Levin

A

Slide 10, lecture 4

Q

SPACE complexity

A

Slide 2, lecture 5

Q

Relationship between TIME and SPACE complexity

A

Slide 3, lecture 5

Q

NP deelverzameling PSPACE

A

Slide 4, lecture 5

Q

TQBF element van PSPACE

A

Slide 5, lecture 5

Q

LADDER_DFA element NPSPACELADDER_DFA element PSPACE

A

Slide 8, lecture 5

Q

Savitch’s theorem + conclusion

A

Slide 11, lecture 5

Q

PSPACE_COMPLETENESS

A

Slide 12, lecture 5

Q

TQBF is PSPACE-Complete

A

Slide 14, lecture 5

Q

Generalized Geography Game

A

Slide 2, lecture 6

Q

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

A

Slide 4, lecture 6

Q

Log Space

A

Slide 6, lecture 6

Q

Log Space properties: L subset of P

A

Slide 7, lecture 6

Q

NL subset of P

A

Slide 8, lecture 6

Q

NL_completess

A

Slide 9, lecture 6

Q

PATH is NL_Complete

A

Slide 10, lecture 6

Q

complement(2SAT) is NL_Complete

A

Slide 11, lecture 6

Q

NL = coNL

A

Slide 12, lecture 6