质疑是进步的阶梯！ 本帖最后由 自由探索 于 2024-6-12 14:13 编辑
顺便说几句，简称NP易产生误会：
1. 非确定性图灵机；
2. 非多项式复杂度；
3. 是否是多项式复杂度【非确定】；（未确定是否有多项式复杂度算法） 涉及具体任务规划、作业调度、货郎担问题，有人说是NP完备的，有人说是NP-hard的。
实际上，言的是不同性质的任务规划、作业调度、货郎担问题。
业内人是清楚差异的，但业外人可能会产生误解。 既然NP-hard问题未必是NP类问题，何必叫NP-hard类型？ 我当年考前刷题老师说不用做北京卷，没有参考价值 自由探索 发表于 2024-6-11 20:44
个人看法：NP≠P
即：P类问题为NP类问题的真子集。
当年洪家威笃定地说，此问题属于不可证问题。:) 而现在，阁下的观点是大多数人的观点。好像正在用借助计算机的方法去证明。 自由探索 发表于 2024-6-11 20:29
千禧年发布的第一名题简言之就是“NP=P？”。
等式说的是所有NP类问题是否都存在多项式复杂度求解算法？
最后一句是很多教科书上的写法。如果了解“多项式相关”这个概念，就不会过分区别此二者了。 自由探索 发表于 2024-6-12 14:11
涉及具体任务规划、作业调度、货郎担问题，有人说是NP完备的，有人说是NP-hard的。
实际上，言的是不同性 ...
前者一般用于YES-NO问题，后者用于最优化问题。例如K团问题，判断有没有K团，通常用前者；而要找最大团，通常用后者。但界限不是绝对的，很多学者随便用，大家也都知道他们指的是什么。 青山人 发表于 2024-6-13 03:38
前者一般用于YES-NO问题，后者用于最优化问题。例如K团问题，判断有没有K团，通常用前者；而要找最大团， ...
不愧是学数学的 ENS 发表于 2024-6-13 09:07
不愧是学数学的
贵校朱洪教授，才是国内最早从事复杂性研究的学者之一。他曾给我看过大名鼎鼎的KNUTH寄给他的支票（因朱教授指出了他那个巨著中的几个错误）。可惜朱教授的学生和学生的学生（最近很火的陈海波），被上交挖走了，复旦计算机损失巨大。 新高考I卷是哪几省在考？
页:
1
[2]