v**m
发帖数: 706 | 1 被老张的事迹深深地感动。极大地激发了我对数学兴趣, 尤其是P v.s. NP problem.
板上有computational complexity的大牛ma? 应该先从哪本专著着手? xiexie.
我就是一小硕码农。 |
w***g
发帖数: 5958 | 2 Sanjeev Arora有本又新又全的书, 还可以免费下载.
【在 v**m 的大作中提到】
: 被老张的事迹深深地感动。极大地激发了我对数学兴趣, 尤其是P v.s. NP problem.
: 板上有computational complexity的大牛ma? 应该先从哪本专著着手? xiexie.
: 我就是一小硕码农。
|
d*****u
发帖数: 17243 | 3 我从精神上支持你
【在 v**m 的大作中提到】
: 被老张的事迹深深地感动。极大地激发了我对数学兴趣, 尤其是P v.s. NP problem.
: 板上有computational complexity的大牛ma? 应该先从哪本专著着手? xiexie.
: 我就是一小硕码农。
|
K****n
发帖数: 5970 | 4 P vs NP 三年前那个HP的人的解后来怎么样了？ |
v**m
发帖数: 706 | 5 那个HP三哥完全是错的，后来他自己把paper withdrawn了。
EE的背景不可能解决这种世界性难题。
【在 K****n 的大作中提到】
: P vs NP 三年前那个HP的人的解后来怎么样了？
|
d**********x
发帖数: 4083 | 6 我去。。
这个坑有啥意义
研究这个不如去看看广义相对论
【在 v**m 的大作中提到】
: 被老张的事迹深深地感动。极大地激发了我对数学兴趣, 尤其是P v.s. NP problem.
: 板上有computational complexity的大牛ma? 应该先从哪本专著着手? xiexie.
: 我就是一小硕码农。
|
v**m
发帖数: 706 | 7 你说P v.s. NP是坑。
那老张搞得数论也是坑？
【在 d**********x 的大作中提到】
: 我去。。
: 这个坑有啥意义
: 研究这个不如去看看广义相对论
|
d**********x
发帖数: 4083 | 8 对于智商低于160的都是坑
这些东西，也就是闲来无事八卦一下，休闲一下
没有必要深入研究
【在 v**m 的大作中提到】
: 你说P v.s. NP是坑。
: 那老张搞得数论也是坑？
|
n******t
发帖数: 4406 | 9 别扯淡了。爱因斯坦当年就是专利局的，那是啥背景？？？
类似现在办公室里面的黑人大妈吧。
【在 v**m 的大作中提到】
: 那个HP三哥完全是错的，后来他自己把paper withdrawn了。
: EE的背景不可能解决这种世界性难题。
|
d******e
发帖数: 7844 | 10 100年前大学教育很普及么？
现在一抓一大把。
【在 n******t 的大作中提到】
: 别扯淡了。爱因斯坦当年就是专利局的，那是啥背景？？？
: 类似现在办公室里面的黑人大妈吧。
|
|
|
d**********x
发帖数: 4083 | 11 爱因斯坦是苏黎世大学的博士。。。
【在 n******t 的大作中提到】
: 别扯淡了。爱因斯坦当年就是专利局的，那是啥背景？？？
: 类似现在办公室里面的黑人大妈吧。
|
S**I
发帖数: 15689 | 12 想骑着自行车上月球？
【在 v**m 的大作中提到】
: 被老张的事迹深深地感动。极大地激发了我对数学兴趣, 尤其是P v.s. NP problem.
: 板上有computational complexity的大牛ma? 应该先从哪本专著着手? xiexie.
: 我就是一小硕码农。
|
d**********x
发帖数: 4083 | 13 我喜欢这个比喻。。
【在 S**I 的大作中提到】
: 想骑着自行车上月球？
|
n*****3
发帖数: 1584 | 14 现在专利局still selective comparing to other government department
【在 n******t 的大作中提到】
: 别扯淡了。爱因斯坦当年就是专利局的，那是啥背景？？？
: 类似现在办公室里面的黑人大妈吧。
|
o*******w
发帖数: 349 | 15 个人浅见，跟着当前在这个领域里的人走不可能有突破。他们之所以在那里耕耘，仅仅
是因为那块地比较软，能挖动，至于宝是不是在那，没人care. 很多人对什么是算法复
杂性都没搞清楚，也能在这个领域里做教研。
所谓复杂性是在保证求到解的情况下算法的复杂性，即最坏复杂性。这只是一个特殊的
情况，一般情况下，应该还有一个参数，alpha, 即求到解的概率(或 proportion), i.
e.
f(n, alpha)
目前大家研究的复杂性是 f(n, 100%), n 是问题规模。个人认为应该研究 f(n, alpha)
同样一个算法A, 对问题P1可能100%求到解，对P2, 可能只有95%。所以说，所谓算法复
杂性研究实际应该叫问题复杂性研究；跟算法无关。
接下来，什么是问题的复杂性。首先，什么是“问题”， 这是我目前考虑的问题。直
觉告诉我应该看 kolmogorov complexity
欢迎讨论
【在 v**m 的大作中提到】
: 被老张的事迹深深地感动。极大地激发了我对数学兴趣, 尤其是P v.s. NP problem.
: 板上有computational complexity的大牛ma? 应该先从哪本专著着手? xiexie.
: 我就是一小硕码农。
|
o*******w
发帖数: 349 | 16 （接着写）
比如 T1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 就不如
T2 = {3, 33, 79, 29, 3, 21, 143, 5, 9，100}
复杂
T1 可以 用 x_（n+1） = x_n + 1， x0 = 1 表示
T2 恐怕只能一个一个的列出这n个元素
也就是说T1可以用很短的表达式定义，而T2必须用比较长的表达式来specify. 表达式
的长度就是kolmogorov的复杂性度量
如果要搜索一个数，T1就只需要 log(n）时间， 而T2 恐怕要 O(n)
如果以多项式步把T2映射到T1, 那么T1和T2是同一类 (这里是log n) 问题。 如果所有
问题都是P则
P=NP. 否则，哪怕有一个问题不是P, 则 P =\= NP
类似的问题，比如 P = log(n)： 如果所有的问题都能以“log n”步映射到T1 则
logN = NP
如果你能构造一个问题例，使得没有任何方法“log n”步映射到T1， 那么
NP =\= logN (or P =\= logN)
i.
alpha)
【在 o*******w 的大作中提到】
: 个人浅见，跟着当前在这个领域里的人走不可能有突破。他们之所以在那里耕耘，仅仅
: 是因为那块地比较软，能挖动，至于宝是不是在那，没人care. 很多人对什么是算法复
: 杂性都没搞清楚，也能在这个领域里做教研。
: 所谓复杂性是在保证求到解的情况下算法的复杂性，即最坏复杂性。这只是一个特殊的
: 情况，一般情况下，应该还有一个参数，alpha, 即求到解的概率(或 proportion), i.
: e.
: f(n, alpha)
: 目前大家研究的复杂性是 f(n, 100%), n 是问题规模。个人认为应该研究 f(n, alpha)
: 同样一个算法A, 对问题P1可能100%求到解，对P2, 可能只有95%。所以说，所谓算法复
: 杂性研究实际应该叫问题复杂性研究；跟算法无关。
|
S**I
发帖数: 15689 | 17 Kolmogorov complexity is not computable.
i.
alpha)
【在 o*******w 的大作中提到】
: 个人浅见，跟着当前在这个领域里的人走不可能有突破。他们之所以在那里耕耘，仅仅
: 是因为那块地比较软，能挖动，至于宝是不是在那，没人care. 很多人对什么是算法复
: 杂性都没搞清楚，也能在这个领域里做教研。
: 所谓复杂性是在保证求到解的情况下算法的复杂性，即最坏复杂性。这只是一个特殊的
: 情况，一般情况下，应该还有一个参数，alpha, 即求到解的概率(或 proportion), i.
: e.
: f(n, alpha)
: 目前大家研究的复杂性是 f(n, 100%), n 是问题规模。个人认为应该研究 f(n, alpha)
: 同样一个算法A, 对问题P1可能100%求到解，对P2, 可能只有95%。所以说，所谓算法复
: 杂性研究实际应该叫问题复杂性研究；跟算法无关。
|
S**I
发帖数: 15689 | 18 Since Kolmogorov complexity is not computable, there is no way to determine
whether T2 has a simpler desciption than enumerating its elements one by one.
【在 o*******w 的大作中提到】
: （接着写）
: 比如 T1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 就不如
: T2 = {3, 33, 79, 29, 3, 21, 143, 5, 9，100}
: 复杂
: T1 可以 用 x_（n+1） = x_n + 1， x0 = 1 表示
: T2 恐怕只能一个一个的列出这n个元素
: 也就是说T1可以用很短的表达式定义，而T2必须用比较长的表达式来specify. 表达式
: 的长度就是kolmogorov的复杂性度量
: 如果要搜索一个数，T1就只需要 log(n）时间， 而T2 恐怕要 O(n)
: 如果以多项式步把T2映射到T1, 那么T1和T2是同一类 (这里是log n) 问题。 如果所有
|
o*******w
发帖数: 349 | 19 Thanks
What do you mean by "Kolmogorov complexity is not computable"?
Could you refer me to some literature
【在 S**I 的大作中提到】
: Kolmogorov complexity is not computable.
:
: i.
: alpha)
|
o*******w
发帖数: 349 | 20 "Kolmogorov complexity is not computable"
You mean it can not Turing-machine way enumerating?
determine
one.
【在 S**I 的大作中提到】
: Since Kolmogorov complexity is not computable, there is no way to determine
: whether T2 has a simpler desciption than enumerating its elements one by one.
|
|
|
o*******w
发帖数: 349 | 21 Got it
Theorem 7. Kolmogorov complexity is not computable.
Proof
Suppose there is a program Q(x) that outputs K(x).
Then, consider the following program:
P(n):
For all x 2 f0; 1gn
If x is the rst string with K(x) n, using the description of Q to check
this.
Output x and halt.
Now, if the sequence of strings outputted for each input length n for P is
x1; x2; : : : ; xn, then K(xn) n.
However, K(xn) c+2 log n { by just using the program above, which has a
constant-size description (given
that the description of Q is just a constant as well), and using 2 log n
bits for encoding n. So we have a
contradiction.
【在 o*******w 的大作中提到】
: Thanks
: What do you mean by "Kolmogorov complexity is not computable"?
: Could you refer me to some literature
|
o*******w
发帖数: 349 | 22 So what?
determine
one.
【在 S**I 的大作中提到】
: Since Kolmogorov complexity is not computable, there is no way to determine
: whether T2 has a simpler desciption than enumerating its elements one by one.
|
S**I
发帖数: 15689 | 23 Both P and NP are Turing decidable, so Kolmogorov complexity cannot be used
to solve P vs. NP problem.
【在 o*******w 的大作中提到】
: So what?
:
: determine
: one.
|
C******s
发帖数: 270 | 24 搞笑。你才是对算法复杂性没有基本常识的，居然也敢夸夸其谈。你说的所有东西都是
业界常识，或者是根本走不通的路（也是常识）。还什么f(n, alpha)，随机算法的基
本分析你都没谱，居然也敢说什么“很多人对什么是算法复杂性都没搞清楚，也能在这
个领域里做教研”。有些人屁股都长脸上么。
i.
alpha)
【在 o*******w 的大作中提到】
: 个人浅见，跟着当前在这个领域里的人走不可能有突破。他们之所以在那里耕耘，仅仅
: 是因为那块地比较软，能挖动，至于宝是不是在那，没人care. 很多人对什么是算法复
: 杂性都没搞清楚，也能在这个领域里做教研。
: 所谓复杂性是在保证求到解的情况下算法的复杂性，即最坏复杂性。这只是一个特殊的
: 情况，一般情况下，应该还有一个参数，alpha, 即求到解的概率(或 proportion), i.
: e.
: f(n, alpha)
: 目前大家研究的复杂性是 f(n, 100%), n 是问题规模。个人认为应该研究 f(n, alpha)
: 同样一个算法A, 对问题P1可能100%求到解，对P2, 可能只有95%。所以说，所谓算法复
: 杂性研究实际应该叫问题复杂性研究；跟算法无关。
|
o*******w
发帖数: 349 | 25 请说具体一点，别扣帽子。 学术讨论吗。我的博士论文就是分析随机算法的。
n^2/alpha
的复杂性见过吗？ 如果你有兴趣，我可以多说一些。
【在 C******s 的大作中提到】
: 搞笑。你才是对算法复杂性没有基本常识的，居然也敢夸夸其谈。你说的所有东西都是
: 业界常识，或者是根本走不通的路（也是常识）。还什么f(n, alpha)，随机算法的基
: 本分析你都没谱，居然也敢说什么“很多人对什么是算法复杂性都没搞清楚，也能在这
: 个领域里做教研”。有些人屁股都长脸上么。
:
: i.
: alpha)
|
C******s
发帖数: 270 | 26 你先扣了顶帽子，把“很多”做算法复杂度的人都拉上船了，还什么学术讨论。
就说你的“个人认为的”什么f(n, alpha)，请问这不是业界常识吗？这是你先发明的
吗？请问BPP、RP、ZPP的定义是什么？
【在 o*******w 的大作中提到】
: 请说具体一点，别扣帽子。 学术讨论吗。我的博士论文就是分析随机算法的。
: n^2/alpha
: 的复杂性见过吗？ 如果你有兴趣，我可以多说一些。
|
