L12 - Problems known to be in P Flashcards
1
Q
What is the Cobham-Edmonds Thesis?
A
Feasible problems are exactly those that are known to be in P.
2
Q
What is a rebuttal to Cobham-Edwards Thesis?
A
- There are feasible problems in EXP with very small input.
- There are infeasible problems in P with very high orders.
3
Q
Give an example of a decision problem…
A
Is D in set A.
4
Q
Give an example of an optimisation problem…
A
Find an optimal S in G.
5
Q
What are some example problems known to be in P?
A
- Shortest path
- Primality
- Fast Fourier
- Max flow
