Intractability

Question 1

• Siano P1 e P2 due problemi appartenenti alla classe NP. (20-01-27,
  
  • Richiamare la nozione di riduzione polinomiale di P1 a P2
  • definizione di problema NPcompleto.
  • Dimostrare che se P1 è NP-completo e se esiste una riduzione polinomiale di P1 a P2, allora anche P2 `e NP-completo. (proof 10.20)
    Perchè è cruciale cha la riduzione utilizzata impieghi tempo polinomiale?

Answer 1

…

Question 2

If an NP-complete problem is in NP then P=NP. (proof 10.21)

Answer 2

….

Question 3

• What does it mean that TM has time complexity T(n)?
• When a problem is in P?
• When a problem is in NP?
• When a problem is NP hard?

Answer 3

…