L11 - Complexity Classes & Turing-Church Thesis

Question 1

Define computable

Answer 1

A problem which there are effective procedures to respond to thgem

Question 2

What is the relationship between Computability and Feasbility?

Answer 2

Computable problems is a superset of Feasible problems.

Question 3

Define Feasbile Problems

Answer 3

Problems that are computable and can be computed in finite time.

Question 4

What are the 3 complexity classes in computational theory?

Answer 4

Linear -> Linear function of N
Polynomial -> Polynomial function of N
Exponential -> Exponential function of N

Question 5

Are EXP problems feasible?

Answer 5

Only for very small inputs

Question 6

Explain the Extended-Turing Church Thesis?

Answer 6

Any computational system can simulate each other up to the polynomial factor.

Question 7

What is the rebuttal to the Extended Turing Church Thesis?

Answer 7

A parallel computer may be able to compute what a sequential system can’t and at a much faster rate.

Question 8

Explain Cookes Thesis…

Answer 8

Any sequential computations can simulate each other up to a polynomial factor.

All sequential systems have similar run time and capability.

Question 9

What is the name of Cookes Thesis?

Answer 9

The Sequential Computation Thesis

Question 10

Define parallel computation…

Answer 10

The process of segmenting a program into sub-processes, each of which is executed concurrently by different processors on a system with shared memory.