9.4 Dealing with NP-hard problems

Question 1

Will Quantum Computers, P=NP, externalities etc. reasonably help you solve your NP hard problem by next week?

Answer 1

Nope.

Question 2

What options do you have to solve NP-hard problems?

Answer 2

1. Approximate solution
2. Exploit properties to give a polynomial solution
3. Try a slower than polynomial algorithm (sub exponential)
4. Otherwise use a SAT solver

Question 3

What are the benifits / challenges of solving an NP-hard problem using an approximate solution?

Answer 3

+ Some problems like minimum vertex cover can be found within a factor of 2 (poly time)
- Others are NP hard within factor of n^0.9999 (independent set)

Question 4

What are some exploitable parameters in graph problems?

Answer 4

• Few edges
• Constant max degree
• Look like tree
• Randomness
• Low tree-width

Question 5

What are parameterised problems (and what are fixed-parameter tractable problems), and how is efficiency defined for them

Answer 5

• Parameterised problem is a special case where a certain parameter is fixed: eg: low max degree
• Use Δ to represent parameter
• Ideally g(Δ) * n^c
• FPT are parameterised problems solvable in poly time. And W[1] hardness is the version of NP-hardness (ie intractable)

Question 6

What is a planar graph?

Answer 6

• Can be drawn without 2 edges overlapping (ex drawing on a map)
• Any non-planar graph has a subform of the below 2

Question 7

How can planar graphs help us (by finding a worse than polynomial time algorithm). And what is the Exponential Time Hypothesis?

Answer 7

• Instead of a^n it is often 2^sqrt(n), which in practice can be much better than exponential

Question 8

Why is using a SAT solver not always a bad idea?

Answer 8

• In the real world can often solve 10s of thousands of variables (exploiting some magical property)