演算法›Ch5 NP Complete Problems
第 3 題/共 30 題
◀ AL 3/30
3. NP-Complete、計算複雜度理論
#AL-05-003中NP-Complete計算複雜度理論

How many of the statements below are known to be true?

  • Every problem in NP is polynomial-time reducible to some NP-hard problem.
  • Every problem in NP is polynomial-time reducible to some NP-complete problem.
  • Every problem in NP is polynomial-time reducible to some problem solvable within polynomial time.
  • Every problem in NP is polynomial-time reducible to some problem solvable within exponential time.
📄 台大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch5 NP Complete Problems
本章題號 · 1–20 / 30