h*y
2 楼
Win a free trip to Rome, Iceland and Las Vegas! 上纪念碑的青蛙们有福了.
Hedgeable.com, an investment start-up that has come up with a neat
gimmick to draw attention to its launch: a nationwide contest to find the
three investors whose portfolios lost the most value between October
2007, when stock markets began to tumble, and March 2009, when
they hit bottom.
The top prize will be a holiday in Rome, the last great empire to collapse
under a mountain of debt, a devalued currency and out-of-control
spending.
Hedgeable.com, an investment start-up that has come up with a neat
gimmick to draw attention to its launch: a nationwide contest to find the
three investors whose portfolios lost the most value between October
2007, when stock markets began to tumble, and March 2009, when
they hit bottom.
The top prize will be a holiday in Rome, the last great empire to collapse
under a mountain of debt, a devalued currency and out-of-control
spending.
H*9
3 楼
由于忙无时间顾及做饭和家务,诚邀小时工来家里做饭,和简单地打扫卫生, 洗衣服。
每周来家里的次数好商量。薪酬高,欢迎洽谈。
有意者请发email联系: g***********[email protected]
每周来家里的次数好商量。薪酬高,欢迎洽谈。
有意者请发email联系: g***********[email protected]
z*n
4 楼
去年10从F1变成H1,我应该符合 dual-status alien,可以申请 first year choice,
填1040表格.
在1040表格 40a 这一栏standard deduction,1040, pg. 36,我看到这么一句话
Do not complete this worksheet if you checked the box on line 39b; your
standard deduction is zero.
而standard deduction 是5700 single, 11400 married。
请问,dual-status alien 这种情况怎么申报deductions?
填1040表格.
在1040表格 40a 这一栏standard deduction,1040, pg. 36,我看到这么一句话
Do not complete this worksheet if you checked the box on line 39b; your
standard deduction is zero.
而standard deduction 是5700 single, 11400 married。
请问,dual-status alien 这种情况怎么申报deductions?
j*5
5 楼
蕃薯岛是林筝儿的新大陆,是海那端的家,是需要转途香港才能抵达的遥远彼岸,是和
阿公相依为命的居所,是故土亲人可遐想可思念在日复一日中等待重逢的信仰。是阿公
和林筝儿共有的一段飘零的,温暖的,安乐的,平淡的,桀荡的人生版图。
蒙在阿公身上的一切传言在林筝儿抵达台北那天就都掀开帐幕。阿公实则住在台北大安
区一间旧式公寓顶楼里,没有所谓的任何家人,就自己一个人伶仃住了几十载。白天阿
公在附近一间商业大楼看管电梯,夜里才回顶楼的寓所。身处闹市,公寓虽只有有6层
楼高,却也是人丁兴旺。住着的多半是热热闹闹的一大家子人,大家习惯看阿公这个外
省老兵一个人进进出出,突然看见他老人家这样一个寻常午后带了个孩子回来,亦都有
些吃惊。
林筝儿不安地静静尾随阿公爬上6楼进了房间。那间小小的寓所有一种上了年纪的气息
,进门一片窄仄的空间只摆了一张桌子,上面零杂摆着虎标万金油,塑料的看不出年代
的眼镜盒,甚至还有浸泡着假牙的一个杯子。寓所有2间隔开的房间,阿公领她进了那
间大室,筝儿一眼就注意到墙上挂着的一把二胡。
“咦?阿公,这是你的琴么?好古早的样子!”
“啊,这是胡琴,阿公用了它很久了。一会阿公拉给你听听。”
就是在那天夜里,林筝儿第一次听到了二胡的声音。阿公拉得痴迷,低垂着脸,眯着眼
开始唉唉唉三声叹息,琴声响起,低浊沧桑。那琴音让林筝儿听起来是那样熟悉,好像
是在哪儿听见过。她的心沉了又远了,缈缈中她想起清晨故乡小天井里的那棵木芙蓉树
,还有后院的老龙眼树也垂枝了,只是今年不知谁会帮母亲爬到高枝去摘那些龙眼。。。
念及于此,林筝儿抽抽噎噎开始哭起来。阿公连忙置了琴在一旁拉她到面前,想她是念
家了,却不知如何宽慰。眼角瞥见筝儿露出衣袖那截瘦骨棱棱的稚气手踝,还有和筝儿
的父亲一样修长白净的指头。只好一任递纸帮筝儿擦眼泪,待她安静下来,这才把琴挂
回墙上。却听见林筝儿在身后怯怯言道:
“阿公——,我想学胡琴。” “你真想拉?” 阿公再确认问。林筝儿用力点了点头。
“拉胡琴好难的哦。。。” 阿公瞪着眼看了看筝儿提高了声调回答。看筝儿迟疑那会
却咧嘴笑了,摸着摸筝儿的脑袋说:“好,好,阿公教!阿公教你拉琴。”
林筝儿就这样开始和阿公拉起二胡了。开学了,阿公让筝儿插班进了附近的一所小学。
白天爷孙两人上班的上班,上学的上学。黄昏两人回到寓所,简单吃过晚饭,若筝儿在
房间里做功课,阿公就在外间小客厅里看看电视等她,有时待筝儿收拾好课业拿着二胡
出来,看阿公已经在电视机前面小寐睡着了,一旁放着的小电扇还在咿咿呀呀转个不停
。林筝儿就悄悄地开了门,带着那把胡琴走到公寓楼顶。望着密密沓沓的台北公寓洋房
,街市里车灯人流不息。拉着拉着林筝儿就身已不在人世间了。月亮出来了,浅浅淡淡
素净清婉挂在夜空。靠近城市边缘有长长低低的云,在那里铺了一条从人间通往天上的
便途。
阿公相依为命的居所,是故土亲人可遐想可思念在日复一日中等待重逢的信仰。是阿公
和林筝儿共有的一段飘零的,温暖的,安乐的,平淡的,桀荡的人生版图。
蒙在阿公身上的一切传言在林筝儿抵达台北那天就都掀开帐幕。阿公实则住在台北大安
区一间旧式公寓顶楼里,没有所谓的任何家人,就自己一个人伶仃住了几十载。白天阿
公在附近一间商业大楼看管电梯,夜里才回顶楼的寓所。身处闹市,公寓虽只有有6层
楼高,却也是人丁兴旺。住着的多半是热热闹闹的一大家子人,大家习惯看阿公这个外
省老兵一个人进进出出,突然看见他老人家这样一个寻常午后带了个孩子回来,亦都有
些吃惊。
林筝儿不安地静静尾随阿公爬上6楼进了房间。那间小小的寓所有一种上了年纪的气息
,进门一片窄仄的空间只摆了一张桌子,上面零杂摆着虎标万金油,塑料的看不出年代
的眼镜盒,甚至还有浸泡着假牙的一个杯子。寓所有2间隔开的房间,阿公领她进了那
间大室,筝儿一眼就注意到墙上挂着的一把二胡。
“咦?阿公,这是你的琴么?好古早的样子!”
“啊,这是胡琴,阿公用了它很久了。一会阿公拉给你听听。”
就是在那天夜里,林筝儿第一次听到了二胡的声音。阿公拉得痴迷,低垂着脸,眯着眼
开始唉唉唉三声叹息,琴声响起,低浊沧桑。那琴音让林筝儿听起来是那样熟悉,好像
是在哪儿听见过。她的心沉了又远了,缈缈中她想起清晨故乡小天井里的那棵木芙蓉树
,还有后院的老龙眼树也垂枝了,只是今年不知谁会帮母亲爬到高枝去摘那些龙眼。。。
念及于此,林筝儿抽抽噎噎开始哭起来。阿公连忙置了琴在一旁拉她到面前,想她是念
家了,却不知如何宽慰。眼角瞥见筝儿露出衣袖那截瘦骨棱棱的稚气手踝,还有和筝儿
的父亲一样修长白净的指头。只好一任递纸帮筝儿擦眼泪,待她安静下来,这才把琴挂
回墙上。却听见林筝儿在身后怯怯言道:
“阿公——,我想学胡琴。” “你真想拉?” 阿公再确认问。林筝儿用力点了点头。
“拉胡琴好难的哦。。。” 阿公瞪着眼看了看筝儿提高了声调回答。看筝儿迟疑那会
却咧嘴笑了,摸着摸筝儿的脑袋说:“好,好,阿公教!阿公教你拉琴。”
林筝儿就这样开始和阿公拉起二胡了。开学了,阿公让筝儿插班进了附近的一所小学。
白天爷孙两人上班的上班,上学的上学。黄昏两人回到寓所,简单吃过晚饭,若筝儿在
房间里做功课,阿公就在外间小客厅里看看电视等她,有时待筝儿收拾好课业拿着二胡
出来,看阿公已经在电视机前面小寐睡着了,一旁放着的小电扇还在咿咿呀呀转个不停
。林筝儿就悄悄地开了门,带着那把胡琴走到公寓楼顶。望着密密沓沓的台北公寓洋房
,街市里车灯人流不息。拉着拉着林筝儿就身已不在人世间了。月亮出来了,浅浅淡淡
素净清婉挂在夜空。靠近城市边缘有长长低低的云,在那里铺了一条从人间通往天上的
便途。
v*m
6 楼
被老张的事迹深深地感动。极大地激发了我对数学兴趣, 尤其是P v.s. NP problem.
板上有computational complexity的大牛ma? 应该先从哪本专著着手? xiexie.
我就是一小硕码农。
板上有computational complexity的大牛ma? 应该先从哪本专著着手? xiexie.
我就是一小硕码农。
s*r
7 楼
按照Laufine的教程,下载相关文件,地图,然后破解。
用的是最新的Mio pocket,
能跑起来,不过没有语音提示,
还有什么设置要改吗?
用的是最新的Mio pocket,
能跑起来,不过没有语音提示,
还有什么设置要改吗?
T*T
8 楼
俺如果能重活一次肯定学医了。 觉得医生跟工程师一样是要研究并解决问题,而且又
能直接帮助到
人,不用全天跟电子仪器打交道,工作稳定,工资高,以后创业也比较容易。
(外加那些小护士。。嘿嘿嘿嘿)
能直接帮助到
人,不用全天跟电子仪器打交道,工作稳定,工资高,以后创业也比较容易。
(外加那些小护士。。嘿嘿嘿嘿)
z*n
10 楼
刚刚研究了519pub,这种情况应该可以申报 first year choice, treated as alien
resident for the whole 2009 year.
所以可以同时拿到standard deduction和5000块 china-US treaty.
不知道我的理解对么?
resident for the whole 2009 year.
所以可以同时拿到standard deduction和5000块 china-US treaty.
不知道我的理解对么?
b*5
11 楼
写的很好看。淡淡的,但有滋味
l*e
13 楼
下载语音包!
z*a
16 楼
我的问题和你差不多,好像要先申extension的吧
x*n
17 楼
写得真好看…闽南风情很足…
【在 j******5 的大作中提到】
: 蕃薯岛是林筝儿的新大陆,是海那端的家,是需要转途香港才能抵达的遥远彼岸,是和
: 阿公相依为命的居所,是故土亲人可遐想可思念在日复一日中等待重逢的信仰。是阿公
: 和林筝儿共有的一段飘零的,温暖的,安乐的,平淡的,桀荡的人生版图。
: 蒙在阿公身上的一切传言在林筝儿抵达台北那天就都掀开帐幕。阿公实则住在台北大安
: 区一间旧式公寓顶楼里,没有所谓的任何家人,就自己一个人伶仃住了几十载。白天阿
: 公在附近一间商业大楼看管电梯,夜里才回顶楼的寓所。身处闹市,公寓虽只有有6层
: 楼高,却也是人丁兴旺。住着的多半是热热闹闹的一大家子人,大家习惯看阿公这个外
: 省老兵一个人进进出出,突然看见他老人家这样一个寻常午后带了个孩子回来,亦都有
: 些吃惊。
: 林筝儿不安地静静尾随阿公爬上6楼进了房间。那间小小的寓所有一种上了年纪的气息
【在 j******5 的大作中提到】
: 蕃薯岛是林筝儿的新大陆,是海那端的家,是需要转途香港才能抵达的遥远彼岸,是和
: 阿公相依为命的居所,是故土亲人可遐想可思念在日复一日中等待重逢的信仰。是阿公
: 和林筝儿共有的一段飘零的,温暖的,安乐的,平淡的,桀荡的人生版图。
: 蒙在阿公身上的一切传言在林筝儿抵达台北那天就都掀开帐幕。阿公实则住在台北大安
: 区一间旧式公寓顶楼里,没有所谓的任何家人,就自己一个人伶仃住了几十载。白天阿
: 公在附近一间商业大楼看管电梯,夜里才回顶楼的寓所。身处闹市,公寓虽只有有6层
: 楼高,却也是人丁兴旺。住着的多半是热热闹闹的一大家子人,大家习惯看阿公这个外
: 省老兵一个人进进出出,突然看见他老人家这样一个寻常午后带了个孩子回来,亦都有
: 些吃惊。
: 林筝儿不安地静静尾随阿公爬上6楼进了房间。那间小小的寓所有一种上了年纪的气息
g*u
20 楼
我好想搞流体力学,当年学的时候感觉真是神一般的科目阿.整个理论建立在一个无法得
到解析解的方程上.....
到解析解的方程上.....
z*n
22 楼
对的,填写4868 表格,申请10月1号以前报税
不过确定你有退税,不然要补交利息
不过确定你有退税,不然要补交利息
j*5
23 楼
谢谢鼓励!初来乍到多有不善,希望不会让大家失望就好~ :)
K*n
24 楼
P vs NP 三年前那个HP的人的解后来怎么样了?
b*r
27 楼
can get return social security tax (for Jan 09-Sep 09)and how?thx
y*n
36 楼
我10月前没有交social security税,10月成为H1B后公司才开始扣,请问如果我和你们
一样,准备延期,然后在今年6月后再按照resident交税,FICA会要求我补交2009年1月
到10月的social security税么?
谢谢
一样,准备延期,然后在今年6月后再按照resident交税,FICA会要求我补交2009年1月
到10月的social security税么?
谢谢
y*n
39 楼
去年10月从F1变成H1B,也不算是resident啊,这就是为什么需要延长报税时间的缘故
么?
dual-status alien是说2009年一段时间nr一段时间resident,但是如果是10月才转,
应该都是nr啊
糊涂了,谢谢解答,我和你情况一样。
【在 z****n 的大作中提到】
: 去年10从F1变成H1,我应该符合 dual-status alien,可以申请 first year choice,
: 填1040表格.
: 在1040表格 40a 这一栏standard deduction,1040, pg. 36,我看到这么一句话
: Do not complete this worksheet if you checked the box on line 39b; your
: standard deduction is zero.
: 而standard deduction 是5700 single, 11400 married。
: 请问,dual-status alien 这种情况怎么申报deductions?
么?
dual-status alien是说2009年一段时间nr一段时间resident,但是如果是10月才转,
应该都是nr啊
糊涂了,谢谢解答,我和你情况一样。
【在 z****n 的大作中提到】
: 去年10从F1变成H1,我应该符合 dual-status alien,可以申请 first year choice,
: 填1040表格.
: 在1040表格 40a 这一栏standard deduction,1040, pg. 36,我看到这么一句话
: Do not complete this worksheet if you checked the box on line 39b; your
: standard deduction is zero.
: 而standard deduction 是5700 single, 11400 married。
: 请问,dual-status alien 这种情况怎么申报deductions?
z*0
42 楼
我也是同样的情况。
也看到有人说即使申请延期,OPT期间的FICA也是可以不交的。
有点儿糊涂了
也看到有人说即使申请延期,OPT期间的FICA也是可以不交的。
有点儿糊涂了
o*w
49 楼
个人浅见,跟着当前在这个领域里的人走不可能有突破。他们之所以在那里耕耘,仅仅
是因为那块地比较软,能挖动,至于宝是不是在那,没人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.
: 我就是一小硕码农。
是因为那块地比较软,能挖动,至于宝是不是在那,没人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
50 楼
(接着写)
比如 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%。所以说,所谓算法复
: 杂性研究实际应该叫问题复杂性研究;跟算法无关。
比如 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
51 楼
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%。所以说,所谓算法复
: 杂性研究实际应该叫问题复杂性研究;跟算法无关。
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
52 楼
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) 问题。 如果所有
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
55 楼
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
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
C*s
58 楼
搞笑。你才是对算法复杂性没有基本常识的,居然也敢夸夸其谈。你说的所有东西都是
业界常识,或者是根本走不通的路(也是常识)。还什么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%。所以说,所谓算法复
: 杂性研究实际应该叫问题复杂性研究;跟算法无关。
业界常识,或者是根本走不通的路(也是常识)。还什么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%。所以说,所谓算法复
: 杂性研究实际应该叫问题复杂性研究;跟算法无关。
相关阅读
工资水平[转载] 求数字信号处理的面试问题2000年始视音频压缩技术的研究重点mpeg4提个建议Re: 怎样能在网上找到别人的博士论文.Re: My God, Am I Self-Plagiarism??remote Code for Daewoo DVN-14F6NJMOSCal -- a small tool for MOS calculationsMPEG技术简介Re: 大家都是怎么review文章的啊?Re: ICASSP录取率挺高的about Var(N(t)?Re: Complex-value SVD C codeRe: 问个review paper的问题Re: ICIP 值得投稿吗?Re: 有人用过auction algorithm吗?Re: 什么是 firmware?关于申请新版的讨论请去BOARDRe: 请教; 写paper时遇到的几个问题,在线等。请不要在本版谈讨无关话题