Fundamental questions (2-5)

Subdecks (5)

5 - Universal Turing machines and undecidability
Z - Old > Introduction to Computation and complexity > Fundamental questions (2-5)
23 cards
4 - Decision problems and languages
Z - Old > Introduction to Computation and complexity > Fundamental questions (2-5)
21 cards
3 - Turing Machines
Z - Old > Introduction to Computation and complexity > Fundamental questions (2-5)
19 cards
2 - Finite state automata
Z - Old > Introduction to Computation and complexity > Fundamental questions (2-5)
16 cards
1 - Motivation and (some background)
Z - Old > Introduction to Computation and complexity > Fundamental questions (2-5)
5 cards

Cards (86)

class P
subsumes all computational tasks that we consider to be efficiently solvable
class NP
subsumes all computational tasks where we can efficiently check whether a proposed solution is correct