讨论:归约
外观
![]() |
本条目页属于下列维基专题范畴: | ||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
![]() | 归约曾于2007年1月8日通过新条目推荐投票,登上维基百科首页的“你知道吗?”栏位。 | ![]() |
![]() |
条目评选
[编辑]新条目推荐
[编辑]本讨论已经结束。请不要对这个存档做任何编辑。
- ~移动自Wikipedia:新条目推荐/候选~(最后修订)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cc/Many-one-reduction.jpg/80px-Many-one-reduction.jpg)
- 什么技巧在分类可计算问题的复杂度时扮演关键角色?(8,216字节,翻译,自荐)-桃子娃 & Neversay 11:46 2007年1月5日 (UTC)
- (!)意见:没有参考资料。加上后即转为(+)支持。--Jnlin 17:58 2007年1月5日 (UTC)
- (:)回应 已增加--桃子娃 & Neversay 18:47 2007年1月5日 (UTC)
- (!)意见 请澄清:首段“可计算问题”应否改为“计算问题”? 此词译自英文本 Computational problem,而英文en:Computational problem#Types of computational problems 一段中有云:...and some computational problems are noncomputable,...。---Hillgentleman | 书 20:10 2007年1月5日 (UTC)
- (:)回应已改正--桃子娃 & Neversay 03:22 2007年1月6日 (UTC)
- (:)回应,的确是计算问题,而非可计算问题,这是笔误,已改正。--桃子娃 & Neversay 15:51 2007年1月6日 (UTC)
- (+)支持--2006年时代杂志风云人物华德禹(来这里喷口水) 05:16 2007年1月6日 (UTC)
- (+)支持--RalfX 08:59 2007年1月8日 (UTC)
- (+)支持--Iflwlou 11:21 2007年1月8日 (UTC)
- (!)意见:没有参考资料。加上后即转为(+)支持。--Jnlin 17:58 2007年1月5日 (UTC)
“将某个可计算问题转换为另一个问题”--此定义或太狭:将一猜想转换成另一猜想算不算? [例:Ribet 曾证:(费马最后定理 <= 谷山-志村猜想)-此为证费马最后定理之一关键,算不算化约?]--Hillgentleman | 书 17:59 2007年1月4日 (UTC)
设有二函数:
- “n- 次元之费马定理”:N----->{0,1}
- 若无整解 则其值为1;
- 若有整解 则其值为0。
- “谷山-志村猜想”:{椭圆曲线} ---> {0,1}
- 若 椭圆曲线之L-函数可配上一模型式,则 其值为 1
- 不然,则 其值为 0。
我们可以讲,Ribet 证明了: 若 此“谷山-志村猜想”函数取常值 1,则“n- 次元之费马定理”函数 取常值 1。 --Hillgentleman | 书 19:57 2007年1月5日 (UTC)
- 我不肯定,因为我没有学过数学的可变换。不过资讯的可变换是有比较特别的意义的。--Jnlin 03:47 2007年1月6日 (UTC)
另外你说的可变换是不是指en:Reduction (mathematics)?--Jnlin 05:15 2007年1月6日 (UTC)- 收回,应该跟你说的不同。资讯的可变换的大部分目的,是要证明复杂度不会大于变换后的已知问题。或许你说的可以另起新题?--Jnlin 05:22 2007年1月6日 (UTC)
定义
[编辑]hard --> 困难 ? (例:NP-hard = NP困难 )
- 你的例子是这样没错。--Jnlin 14:55 2007年1月6日 (UTC)
- 是我翻到昏头了,笔误已改正 --桃子娃 & Neversay 17:13 2007年1月6日 (UTC)
reduction的定义
[编辑]Hilgentleman兄的说法是正确的,证明了Taniyama-Shimura Conjecture(所有Q上的椭圆曲线是模的)等于证明了Fermat's Last Theorem,它们之间是以这一页最下方的形式来连结的。根据reduction的定义,Fermat's Last Theorem reduces to Taniyama-Shimura Conjecture. 但本条目的reduce注重在计算复杂度理论上,所以讨论的reduction都跟区分复杂度类有关,因此介绍一般性的reduction可能要另开条目。--桃子娃 & Neversay 17:11 2007年1月6日 (UTC)
详例
[编辑]不解:“仲裁机器S现在可运算R(N)以验证被N接受的语言是否为空集合。” -- 图灵机S(M,w):之输入为图灵机M与字串w;R(N)是什么?如何将之输入S?--Hillgentleman | 书 17:36 2007年1月6日 (UTC)
- 因为我将evaluate误译成运算,正确的词应该是评估或评量。R是仲裁机器,因此R(N)的输出是N可接受(停机)的语言集合。--桃子娃 & Neversay 18:02 2007年1月6日 (UTC)