Define the complexity class NP

?
  • Created by: 4medaa
  • Created on: 22-12-18 20:01
Define the complexity NP
A language L is in NP if there is a non-deterministic Turing Machine that decides it with time complexity in O(nr) where r is independent of n. The class of all languages decidable in non-deterministic polynomial time is denoted NP
1 of 5
State the halting problem
Given TM M, with alphabet Σ, together with u∈Σ*, will the computation of M with input u halt?
2 of 5
What is a Universal Turing Machine
A Universal Turing machine is TM that simulates the computations performed by an arbitrary turing machine.
3 of 5
State a consequence of Church’s Thesis
An algorithmic procedure that can be carried out by a human being or by a computer can be carried out by a Turing Machine
4 of 5
What does your answer say about the limits of computation?
There are well formed computational questions whose answers cannot be computed (using a TM)
5 of 5

Other cards in this set

Card 2

Front

State the halting problem

Back

Given TM M, with alphabet Σ, together with u∈Σ*, will the computation of M with input u halt?

Card 3

Front

What is a Universal Turing Machine

Back

Preview of the front of card 3

Card 4

Front

State a consequence of Church’s Thesis

Back

Preview of the front of card 4

Card 5

Front

What does your answer say about the limits of computation?

Back

Preview of the front of card 5

Comments

No comments have yet been made

Similar Computing resources:

See all Computing resources »See all Theory Of Computation resources »