未來數學家的挑戰 -- NP-hardness 與圍棋 - The Diigo Meta page

• 03 Nov 11
  

  Jiaxing Zhang

  數學

• 23 Dec 07
  

  York Jong

  NP algorithm complexity computation math

  • 定義： 若 x 為一 NP-hard 問題，則若 NP ，則 。 

     

      

     也就是說，即使 P=NP，x 還不一定屬於 P，但 NP, 則 x 絕不比 NP 的問題容易
  • 注意在上式中 PSPACE-complete PSPACE，即 PSPACE-complete 是 PSPACE 中的難題，但 PSPACE-hard 不一定屬於 PSPACE

Would you like to comment?

Join Diigo for a free account, or sign in if you are already a member.