PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 算法 P/NP/NPC
楼主:
clonsey1314
(Clonsey)
2017-11-30 19:55:07
想问一下
同样在NPC的问题里, 都视为一样难吗?
那这样所有P里的问题也都视为一样难吗?
例如一个问题O(n)可解, 另一个O(n^2)可解
这样也视为一样难吗?
作者:
nat99up
(NAt)
2017-11-30 21:09:00
一样难是因为可以互相reduction在P里面谈reduce没有什么意义因为是规定多项式时间内可以转换但你解决的时间就是已经多项式时间了
作者:
FRAXIS
(喔喔)
2017-11-30 21:27:00
以 polynomial-time reduction 的观点来看 NPC 都是一样难但是有不同的 reduction 定义 可以区分 NPC 问题的难度
作者:
alan23273850
2017-11-30 21:44:00
感谢楼上算法大大,长知识惹
作者:
can18
(18号)
2017-11-30 22:07:00
感谢F大 长知识了
作者:
nat99up
(NAt)
2017-12-01 11:01:00
感谢F大指正!
作者:
FRAXIS
(喔喔)
2017-12-01 11:04:00
举例来说,我们可以用 Log-space reduction 来定义 NPC
https://en.wikipedia.org/wiki/Log-space_reduction
有些书是用 log-space reduction 来定义 NPC但是 log-space reduction 和 polynomial-time reduction定义出来的 NPC 是不是等价 仍然是 open question
继续阅读
[理工] 离散 无理数证明
clonsey1314
[请益] 补数基本概念
wayneshiau
[理工] 计组 srl sll
nO25948
Re: [理工] OS fork()的问题
alan23273850
[理工] OS fork()的问题
s90210jackle
[理工] 简单流力
wadeinthe
[理工] 机率 积分问题
pureblue1234
[理工]94交大计组 cpi
gary70812
[理工] 离散生成函数
qwer911
[理工] 复杂度计算一题
TMDTMD2487
Links
booklink
Contact Us: admin [ a t ] ucptt.com