据说今年高考全国卷数学卷较难

自由探索

质疑是进步的阶梯！

自由探索

顺便说几句，简称NP易产生误会：

1. 非确定性图灵机；
2. 非多项式复杂度；
3. 是否是多项式复杂度【非确定】；（未确定是否有多项式复杂度算法）

自由探索

涉及具体任务规划、作业调度、货郎担问题，有人说是NP完备的，有人说是NP-hard的。

实际上，言的是不同性质的任务规划、作业调度、货郎担问题。

业内人是清楚差异的，但业外人可能会产生误解。

自由探索

既然NP-hard问题未必是NP类问题，何必叫NP-hard类型？

空号BLANK

我当年考前刷题老师说不用做北京卷，没有参考价值

青山人

自由探索 发表于 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团，通常用前者；而要找最大团，通常用后者。但界限不是绝对的，很多学者随便用，大家也都知道他们指的是什么。

ENS

青山人 发表于 2024-6-13 03:38
前者一般用于YES-NO问题，后者用于最优化问题。例如K团问题，判断有没有K团，通常用前者；而要找最大团， ...

不愧是学数学的

青山人

ENS 发表于 2024-6-13 09:07
不愧是学数学的

贵校朱洪教授，才是国内最早从事复杂性研究的学者之一。他曾给我看过大名鼎鼎的KNUTH寄给他的支票（因朱教授指出了他那个巨著中的几个错误）。可惜朱教授的学生和学生的学生（最近很火的陈海波），被上交挖走了，复旦计算机损失巨大。

关注人

新高考I卷是哪几省在考？