作者ajnightmare (阿华田)
看板NTUBIME100HW
标题[演算] P, NP, NPC, NP-hard
时间Sun May 24 12:05:08 2009
P是?
一个可以在O(n^k),k是一个常数,解出的问题
NP是?
非决定性多项式时间(non-deterministic polynomial time)
NP的问题是所有会回答"是"或"否"问题的集合,
而且,当它回答"是"的时候,答案确实是"是",而且可以在
多项式时间被验证.
当它回答"否"的时候,并没有方法可以证明答案是不是正确的.
Nondeterministic algorithm
一个演算法具有一个或多个路径选择点,每个路径都有可能会走
但没任何方法知道会走哪一条
NPC是?
假如有个问题C满足两个条件
1.C属於NP问题
2.任何的NP问题 can be reduced to C
定义C就是NPC的问题
意思是C就是NP集合中最难的问题.
NP-hard是?
假如有个问题H满足
一个NPC的问题 can be reduced to H.
定义H是NP-Hard的问题
因为H至少要跟NP中最难的问题一样难.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.7.59
1F：→ ajnightmare:NP我似乎只有解释NP的问题而没解释本身 05/26 16:02
2F：推 aldreamp:"任何的NP问题 can be reduced from C" 是C比较简单吗? 05/30 14:40
3F：推 aldreamp:一个NPC的问题 can be reduced "from" H 写to呢? 05/30 14:42
4F：推 jane050177:NP: a class of problem which there exits a 05/31 11:12
5F：→ jane050177:nondeterministic algo which running time is 05/31 11:12
6F：→ jane050177:polynomial in size of inputs 05/31 11:12
※ 编辑: ajnightmare 来自: 58.114.208.7 (06/18 22:23)
※ 编辑: ajnightmare 来自: 58.114.208.7 (06/19 00:24)