T*******x 发帖数: 8565 | 1 我个人认为这是一条公理。也就是说1,它永远不会和事实相矛盾,2,它符合人类认知
精神。
说一下这个论断的含义。首先,任何数学问题的解决,都是靠某种分类方案,然后在类
空间上枚举,也就是一个一个来。
NP问题是说,一个问题的“直接”枚举空间的大小随着问题“尺度”的增长以指数方式
增长。举个例子,邮差问题。邮差送信,假如有10个客户,住在不同的地方,客户之间
存在固定的连接道路,邮差要设计一条最佳路径,每个客户都送到,而且走的路程最短
。10就是这个问题的尺度,简单枚举空间就是全部长度为10的路径空间,或者10个客户
的全排列空间。这个问题如果把全部路径列出来,一条一条来看的话,是很容易找出最
佳路径的。问题的难度在于简单枚举空间太大,关键是它随着问题的尺度指数增长。
换句话说,NP问题也就是问题的不加任何智能分类的原始解决方法。
P问题就是原问题在简单枚举空间上再加以分类,问题在新的类空间上可以枚举解决,
而新的类空间比简单枚举空间小多了,关键是它随问题尺度的增长方式小于指数增长,
也就是某种幂次方增长。如果找到了这样的分类方法,那么原问题既是NP问题也是P问
题。
P=NP作为公理是说,任何NP问题一定存在简单枚举空间上的某种分类方式,小于指数增
长,原问题可以在新的类空间枚举解决。
比较一下几个数量的大小:问题尺度,这个一般不大,可能十几个,几十个。简单枚举
空间的大小,这个就大多了,这个是问题空间的幂集,也就是所有子集的集合。简单枚
举空间之上的分类方式的空间,这就更大了,这是简单枚举空间的幂集,也就是原问题
空间的幂集的幂集。 |
P***y 发帖数: 2885 | 2 P=/=NP是绝大多数相关研究人士的直觉吧。请不要民科了。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我个人认为这是一条公理。也就是说1,它永远不会和事实相矛盾,2,它符合人类认知 : 精神。 : 说一下这个论断的含义。首先,任何数学问题的解决,都是靠某种分类方案,然后在类 : 空间上枚举,也就是一个一个来。 : NP问题是说,一个问题的“直接”枚举空间的大小随着问题“尺度”的增长以指数方式 : 增长。举个例子,邮差问题。邮差送信,假如有10个客户,住在不同的地方,客户之间 : 存在固定的连接道路,邮差要设计一条最佳路径,每个客户都送到,而且走的路程最短 : 。10就是这个问题的尺度,简单枚举空间就是全部长度为10的路径空间,或者10个客户 : 的全排列空间。这个问题如果把全部路径列出来,一条一条来看的话,是很容易找出最 : 佳路径的。问题的难度在于简单枚举空间太大,关键是它随着问题的尺度指数增长。
|
l**p 发帖数: 6080 | 3 发明p=np本身就是cs的一个笑料
【在 P***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : P=/=NP是绝大多数相关研究人士的直觉吧。请不要民科了。
|
a****o 发帖数: 6612 | 4 如果分类本身就是一个NP问题呢? 实际上分类问题本身可能是不可判定问题。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我个人认为这是一条公理。也就是说1,它永远不会和事实相矛盾,2,它符合人类认知 : 精神。 : 说一下这个论断的含义。首先,任何数学问题的解决,都是靠某种分类方案,然后在类 : 空间上枚举,也就是一个一个来。 : NP问题是说,一个问题的“直接”枚举空间的大小随着问题“尺度”的增长以指数方式 : 增长。举个例子,邮差问题。邮差送信,假如有10个客户,住在不同的地方,客户之间 : 存在固定的连接道路,邮差要设计一条最佳路径,每个客户都送到,而且走的路程最短 : 。10就是这个问题的尺度,简单枚举空间就是全部长度为10的路径空间,或者10个客户 : 的全排列空间。这个问题如果把全部路径列出来,一条一条来看的话,是很容易找出最 : 佳路径的。问题的难度在于简单枚举空间太大,关键是它随着问题的尺度指数增长。
|
a****o 发帖数: 6612 | 5 不了解才会觉得可笑。
【在 l**p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 发明p=np本身就是cs的一个笑料
|
xt 发帖数: 17532 | 6 你能证明这个?那你要发大财啊! 现有的所有加密方式都成了渣
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我个人认为这是一条公理。也就是说1,它永远不会和事实相矛盾,2,它符合人类认知 : 精神。 : 说一下这个论断的含义。首先,任何数学问题的解决,都是靠某种分类方案,然后在类 : 空间上枚举,也就是一个一个来。 : NP问题是说,一个问题的“直接”枚举空间的大小随着问题“尺度”的增长以指数方式 : 增长。举个例子,邮差问题。邮差送信,假如有10个客户,住在不同的地方,客户之间 : 存在固定的连接道路,邮差要设计一条最佳路径,每个客户都送到,而且走的路程最短 : 。10就是这个问题的尺度,简单枚举空间就是全部长度为10的路径空间,或者10个客户 : 的全排列空间。这个问题如果把全部路径列出来,一条一条来看的话,是很容易找出最 : 佳路径的。问题的难度在于简单枚举空间太大,关键是它随着问题的尺度指数增长。
|
T*******x 发帖数: 8565 | 7 我忘了说了,这个也证明不了。既证明不了,也不能否证。所以它才有作为公理的基础。
【在 xt 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你能证明这个?那你要发大财啊! 现有的所有加密方式都成了渣
|
T*******x 发帖数: 8565 | 8 P=NP作为公理的意思是说,一个问题如果你没有找到P的解决方法,那你还得继续去找。
【在 P***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : P=/=NP是绝大多数相关研究人士的直觉吧。请不要民科了。
|
T*******x 发帖数: 8565 | 9 这个地方我觉得要提出具体的问题,什么问题的分类问题,得具体到这个程度。问题一
明确,能不能解决也就看得更清楚了。
这个地方我也没想清楚,但是我感觉现代数学提出的一些公理,就是在提出明确的问题
。把笼统的问题领域再细化一下,看看哪些是能明确提出的,哪些不是,这个分界处就
有个公理。我这段话说的不是数学,是感觉。
【在 a****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果分类本身就是一个NP问题呢? 实际上分类问题本身可能是不可判定问题。
|
l***o 发帖数: 7937 | 10 看到老民科每天在这里谈一些狗屁玩意儿就好笑。
: P=/=NP是绝大多数相关研究人士的直觉吧。请不要民科了。
【在 P***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : P=/=NP是绝大多数相关研究人士的直觉吧。请不要民科了。
|
|
|
l***o 发帖数: 7937 | 11 看到老民科每天在这里谈一些狗屁玩意儿就好笑。
: P=/=NP是绝大多数相关研究人士的直觉吧。请不要民科了。
【在 P***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : P=/=NP是绝大多数相关研究人士的直觉吧。请不要民科了。
|
T*******x 发帖数: 8565 | 12 不笑不足以为道。你这个注解加的好。
【在 l***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看到老民科每天在这里谈一些狗屁玩意儿就好笑。 : : : P=/=NP是绝大多数相关研究人士的直觉吧。请不要民科了。 :
|
n********g 发帖数: 6504 | 13 你是学EE/物理的吧。“蛮力”这个词是学物理常见的误区。
“蛮力”这个词来自俄文。鹅毛告诉俺,等同于傻逼的意思。BTW,苏俄出了这么多科
学大师的民族,被看成傻大粗,都拜托朱可夫这个有名的“蛮力”大师(aka 傻逼)。
“蛮力”对应中文可以用“水银泄地”形容。就是用足够多的事例(分子)去覆盖问题
空间(压力测试),然后找出哪里漏了。大致就是朱可夫打仗的办法,如一个集团军对
付日军一个团,柏林死伤50万等等。
而哪怕最低级的CS学生都知道,问题空间里很多组合是不需要试的。专业术语叫做“剪
枝”。就是引入测度,告诉计算机:你个傻逼,这个方向肯定不对别浪费CPU周期了。
用毛轮的话:这叫作具体问题具体分析。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我个人认为这是一条公理。也就是说1,它永远不会和事实相矛盾,2,它符合人类认知 : 精神。 : 说一下这个论断的含义。首先,任何数学问题的解决,都是靠某种分类方案,然后在类 : 空间上枚举,也就是一个一个来。 : NP问题是说,一个问题的“直接”枚举空间的大小随着问题“尺度”的增长以指数方式 : 增长。举个例子,邮差问题。邮差送信,假如有10个客户,住在不同的地方,客户之间 : 存在固定的连接道路,邮差要设计一条最佳路径,每个客户都送到,而且走的路程最短 : 。10就是这个问题的尺度,简单枚举空间就是全部长度为10的路径空间,或者10个客户 : 的全排列空间。这个问题如果把全部路径列出来,一条一条来看的话,是很容易找出最 : 佳路径的。问题的难度在于简单枚举空间太大,关键是它随着问题的尺度指数增长。
|
T*******x 发帖数: 8565 | 14 测度什么意思你清楚吗?
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是学EE/物理的吧。“蛮力”这个词是学物理常见的误区。 : “蛮力”这个词来自俄文。鹅毛告诉俺,等同于傻逼的意思。BTW,苏俄出了这么多科 : 学大师的民族,被看成傻大粗,都拜托朱可夫这个有名的“蛮力”大师(aka 傻逼)。 : “蛮力”对应中文可以用“水银泄地”形容。就是用足够多的事例(分子)去覆盖问题 : 空间(压力测试),然后找出哪里漏了。大致就是朱可夫打仗的办法,如一个集团军对 : 付日军一个团,柏林死伤50万等等。 : 而哪怕最低级的CS学生都知道,问题空间里很多组合是不需要试的。专业术语叫做“剪 : 枝”。就是引入测度,告诉计算机:你个傻逼,这个方向肯定不对别浪费CPU周期了。 : 用毛轮的话:这叫作具体问题具体分析。
|
n********g 发帖数: 6504 | 15 无所谓,借用一下。我学这个的时候当年CS里没名字。咳咳,其实连油印课本讲义都没
有。但每一个组合总要量化判断一下。举例说这个组合的后继最好的可能是啥。如果不
高于当前找到的就不用浪费时间了。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 测度什么意思你清楚吗?
|
n********g 发帖数: 6504 | 16 另外,别想多了。我不是说你“蛮力”。
只是指出你这些想法前人想过,有典故。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 测度什么意思你清楚吗?
|
T*******x 发帖数: 8565 | 17 一个集合上的测度,是该集合幂集上的一个函数,正实函数。也就是给每个子集赋值,
标记子集的大小。要满足一些合理性条件。
你的用法大概有这个意思。
【在 n********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 无所谓,借用一下。我学这个的时候当年CS里没名字。咳咳,其实连油印课本讲义都没 : 有。但每一个组合总要量化判断一下。举例说这个组合的后继最好的可能是啥。如果不 : 高于当前找到的就不用浪费时间了。
|
e****w 发帖数: 1565 | 18 p=Np非常好证
你只要证能能能在现在的NPhard 问题里证明一一个可以用在多项式时间解决就可以了
lol
干净去证吧 别瞎逼逼了 |
T*******x 发帖数: 8565 | 19 那你试试?
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : p=Np非常好证 : 你只要证能能能在现在的NPhard 问题里证明一一个可以用在多项式时间解决就可以了 : lol : 干净去证吧 别瞎逼逼了
|
T*******x 发帖数: 8565 | 20 你这样,你解方程啊,当N=1的时候,p=Np。呵呵。
【在 e****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : p=Np非常好证 : 你只要证能能能在现在的NPhard 问题里证明一一个可以用在多项式时间解决就可以了 : lol : 干净去证吧 别瞎逼逼了
|
e****w 发帖数: 1565 | 21 我说了个怎样让人信服的方法让你这个傻屌自己去证P=NP
你个傻屌扯了一大堆狗屁倒灶的东西有用吗?
: 你这样,你解方程啊,当N=1的时候,p=Np。呵呵。
【在 T*******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这样,你解方程啊,当N=1的时候,p=Np。呵呵。
|
I******i 发帖数: 203 | |