讨论:归约

条目评选

新条目推荐

本讨论已经结束。请不要对这个存档做任何编辑。

～移动自Wikipedia:新条目推荐/候选～（最后修订）

• 什么技巧在分类可计算问题的复杂度时扮演关键角色？（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)

～移动完毕～--天上的云彩 云端对话 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}
  • 若$x^{n}+y^{n}=z^{n}$无整解 则其值为１；
  • 若$x^{n}+y^{n}=z^{n}$有整解 则其值为０。
• “谷山－志村猜想”：{椭圆曲线} ---> {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)