L13 - Problems now known to be in P Flashcards
1
Q
What does it mean if a problem is not known to be in P?
A
The problem may or may not be solvable in polynomial time, but there is not current algorithm that does this.
2
Q
What are 4 examples of problems not known to be in P?
A
- TSP
- Graph colouring
- Max cut
- 0-1 Knapsack
- Time tabling
3
Q
What is the time complexity of TSP using brute force?
A
O(N!)
4
Q
How can the complexity of TSP be reduced to EXP?
A
Dynamic Programming
5
Q
What are some ways we can approach problems not known to be in P?
A
- Approximation algorithms
- Algorithms that generate solutions quickly on average
- Algorithms that we know are close to being accurate
