Week 8 Flashcards
What problems are not known to be in P?
Travelling salesperson
Bin-pacing
Graph colouring
Timetabling
What is the travelling salesman?
Decide if a salesperson can complete a round trip of N cities within a given mileage allowance, visiting each city exactly once.
What is the Hamilton cycle problem
In TSP it decides whether a round trip that visits each city exactly once is even possible.
What is the Bin-packing problem?
Decide if T trucks, each of which can carry a load W can carry N crates of different weights.
What is the Knapsack problem?
0-1 knapsack problem is to pack a backpack that can hold weight W with items of different weights and values.
What is graph colouring problem
Assign colours to each vertex of a graph G such that no adjacent vertices get same colour. The aim is to minimize the number of colours while coloring a graph.
What is the timetabling problem
The timetabling problem is to create a timetable so that given a list of modules, a list of students enrolled on those modules, and the timeslots available, no student has a clash.
How do we make progress for problems not in P
Use algorithms that find:
solutions that are approximate
solutions that come quickly on average
solutions that are probably correct.
Explain solutions that are approximate
One way to make progress is to find solutions that are
approximate — a reasonably short tour or a timetable with a
few clashes may be better than nothing.
Explain solutions that come quickly on average
Another way to make progress is to find solutions that come
quickly on average — typical data may not cause a problem.
Explain solutions that are probably correct
Another way to make progress is to find solutions that are
probably correct — there is a very small chance the solution
will be incorrect.
What is the complexity class NP
NP is for problems for which there are no known algorithms for finding solutions in P, but there are algorithms for checking solutions in P.
What does NP stand for
Non-deterministic polynomial time. It is the collection of decision problems that can be solved by a
non-deterministic machine in polynomial time.
Whats an example of NP problem
Sudoku
What are NP complete problems?
The hardest problems in NP. If an algorithm in P was found for it, there would be algorithms in P found for all of them.
What is the SAT problem?
The SAT problem is to assign values to the variables of a
boolean formula 𝜑 that make it true.
For
𝜑 = (¬𝑝 ∨ 𝑞) ∧ (¬𝑞 ∨ 𝑟) ∧ (𝑝 ∨ 𝑞 ∨ ¬𝑟)
take 𝑝 = false and 𝑞 = true, and 𝑟 = true.
The SAT problem is NP-complete.
What are other NP-complete problems?
Clique
String correction problem
Rubik’s cube problem
Subgraph isomorphism problem
What is clique problem?
Find a fully connected subgraph in a graph. It is NP-complete.
What is the string correction problem?
Compute the shortest edit distance between one string and another. e.g. rain -> shine is 4 steps
Replace Delete Insert Copy
What is the rubiks cube problem?
Compute the minimal unscrambling action needed to make all of the faces the same.
What is Subgraph Isomorphism problem?
Determine whether one graph G contains a subgraph that is isomorphic to H. It is NP complete.
How do we solve NP-complete problems?
Exact algorithms
Approximate algorithms
Probablistic algorithms
What is an exact algorithm?
Usually only work for relatively small input
Travelling salesman has (n-1)!/2 possible tours, so O(n!). Using dynamic programming to remember subtours makes this O(n^2 2^N)
What is an approximate algorithm?
Finds a decent solution that is not optimal but can be computed in P time.
What is a probablistic algorithm?
Finds a solution that is probably a good one.
What is a probablistic algorithm?
Finds a solution that is probably a good one.
