维基百科

讨论:归约

了解更多有关此页面的信息
          本条目属于下列维基专题范畴：
数学专题 （获评未评级、低重要度）
本条目属于数学专题范畴，该专题旨在改善中文维基百科数学类内容。如果您有意参与，请浏览专题主页、参与讨论，并完成相应的开放性任务。
 未评级未评  根据专题质量评级标准，本条目尚未接受评级。
 低  根据专题重要度评级标准，本条目已评为低重要度。
电脑和信息技术专题 （获评低重要度）
本条目属于电脑和信息技术专题范畴，该专题旨在改善中文维基百科信息技术相关条目类内容。如果您有意参与，请浏览专题主页、参与讨论，并完成相应的开放性任务。
 未评级未评  根据专题质量评级标准，本条目尚未接受评级。
 低  根据专题重要度评级标准，本条目已评为低重要度。

本页面曾于2007年1月3日被送交存废讨论，讨论结果为保留。

条目评选

编辑

新条目推荐

编辑
本讨论已经结束。请不要对这个存档做任何编辑。
～移动自Wikipedia:新条目推荐/候选～（最后修订）
 
～移动完毕～--天上的云彩 云端对话 11:48 2007年1月8日 (UTC)

“将某个可计算问题转换为另一个问题”--此定义或太狭：将一猜想转换成另一猜想算不算？ ［例：Ribet 曾证：（费马最后定理 <= 谷山-志村猜想）－此为证费马最后定理之一关键，算不算化约？］--Hillgentleman | 书 17:59 2007年1月4日 (UTC)

这条目是指计算理论(Computing Theory)的可变换，跟数学的可变换应该不同。--Jnlin 17:53 2007年1月5日 (UTC)
Jnlin,“应该不同”－ 你肯不肯定不同？

设有二函数：

  • “n- 次元之费马定理”：N----->{0,1}
    • 若 无整解 则其值为１；
    • 若 有整解 则其值为０。
  • “谷山－志村猜想”：{椭圆曲线} ---> {0,1}
    • 若 椭圆曲线之L-函数可配上一模型式，则 其值为 １
    • 不然，则 其值为 ０。

我们可以讲，Ribet 证明了： 若 此“谷山－志村猜想”函数取常值 １，则“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)
添加话题
检索自“https://zh.wikipedia.org/w/index.php?title=Talk:歸約&oldid=81347141”
返回到“歸約”页面。