试析优选论的计算复杂性问题
马秋武 吴力菡
文章首先介绍有关计算复杂性的相关概念，然后针对优选论是否具有计算难解的问题，概述各方面的论点，最后对优选论的算法等其他相关问题进行概括和总结。优选论；计算复杂性H017A010808
优选论（Optimality Theory，简称OT）自20世纪90年代诞生开始就引起国内外研究者的广泛关注。在保留其核心理论框架的前提下，优选论经历了多次技术上的调整以解释更多的音系问题，并被拓展到音系以外的其他领域，如句法、语用等，可见其理论思想具有较强的活力，其操作模式具有开放性，因而至今仍然是语言学界的主流理论之一。但与此同时，20多年来，围绕优选论产生的各种质疑和争论也从未间断过，优选论在理论和应用上一直面临着不少挑战。其中，优选论所具有的独特的操作模式和计算方法引发了近年来在计算音系学领域中对于优选论计算复杂性（computational complexity）问题的热议。所涉及的问题包括：优选论中的生成问题是否属于NP难解问题？学习者如何习得计算量庞大的制约条件等级排列以及底层形式？等等。对此，Eisner（1997）和Isardi（2006a， b）等人试图论证优选论在计算上是不可解的（intractable）从而否定优选论的运行模式。Kornai（2006a， b），Tesar（1995），Heinz， et al（2009），Riggle（2009），Kager（1999），Prince and Smolensky（1993/2004）等人则从不同角度对之进行反驳，支持优选论。本文首先介绍有关计算复杂性的相关概念，然后概述来自双方的论点，进而对优选论的其他相关问题进行总结。
一、 有关计算性的相关概念
早在20世纪50年代末，Chomsky便将数学思想引入到语言学研究当中，将二者结合起来，形成一种形式语言学理论。这种形式语法具有算法（algorithms）的特点。换言之，语法作为一种生成句子的装置，很像数学中的“算法”过程（陆极致1990：171， 182183）。
所谓算法指的是一系列解决问题的清晰指令，是一个有限规则的有序集合，对于某类问题的初始输入，它能在有限时间内机械地逐步计算，在有限步骤后计算终止，获得一个输出结果。一个问题可以有多种算法。一个算法的优劣可以用时间复杂度（timecomplexity）和空间复杂度（spacecomplexity）来衡量，分别表示完成计算过程所需的总步数以及所用存贮的单元数（Mitkov 2003：178； Linz 2001：343344； 堵丁柱等 2002：17； 赵瑞清、孙宗智 1989： 5457； 张泽增 1989：4）。
时间复杂度关注的是当某个问题的规模扩大后，程序运行所需的时间增长得有多快。这里需要区分多项式（polynomial）时间算法和指数（exponential）时间算法。形如n2的多项式中，表示问题规模或大小（size）的参数n在底数位置；形如2n的指数时间算法中，n在指数位置，随着n的变大，它所需的计算时间以爆炸性的速率迅速增加。例如，在一台每秒做1亿次运算的计算机上，对于时间复杂度分别是n3和3n的算法来说，当n达到60时，它们所需的计算时间分别为2.16×10-3秒和1.3×1011世纪。显然，当n较大时，后者所需的时间是计算机无法承受的。
马秋武等：试析优选论的计算复杂性问题所谓问题，指的是从输入映射到其结果（即输出）的函数。设f为多项式函数，n为输入的长度，当且仅当该问题存在着能在f（n）步之内完成该函数的图灵机（Turing machine）时，这一问题便“在多项式时间内可计算”（Heins， et al 2009）。多项式时间算法（或称有效果算法）被认为是好的算法，计算机可以执行。有好的算法的问题是易解（tractable）的，属于P类问题，即在确定型图灵机上有多项式时间算法（实际可用的算法）。若一个问题找不到或尚未找到有效算法，则称为难解的（intractable），属于“非确定多项式算法（nondeterministic polynomialtime algorithm）”，简称为NP类问题。如果所有NP问题都能规约（reduce）到某一种问题，那么这种问题称为NP难解（NPhard）问题（张泽增 1989：138； 张立昂 1996：227228）。
二、 优选论的计算复杂性问题
1. 经典优选论的运算模式
优选论把语言形式看成是制约条件交互作用的结果。其语法体系包括三大部分：生成器（Generator）、制约条件集合（The Constraint Set）和评估器（Evaluator），通常分别简写为GEN，CON，EVAL。它的运算模式如下：生成器为某个输入项生成一系列可能的输出项，即候选项集合（candidate set）；然后，评估器根据CON所提供的制约条件等级体系排列筛选出最优的候选项，即最终的输出项。
较之传统的基于规则的音系分析方法，优选论在语言类型的问题上表现出了强大的解释力，但其代价是计算的复杂度增加了，难以进行人工计算。有人认为，生成器所具有的自由分析原则（freedom of analysis）会产生无限多的结构，而计算无限数量的候选项需要无限的时间（Kager 1999：25），这必然会导致不可计算，故优选论不能成为一个合理的言语产出或感知模型。Idsardi（2006a）结合了计算复杂性理论，试图论证经典优选论的生成问题属于NP难解问题。该篇文章引发了对优选论计算性问题的关注和热烈讨论。以下分别介绍Idsardi对优选论不可解的证明以及来自各方支持优选论的论点。
2. 优选论计算不可解的论证
Garey and Johnson （1979）提出了证明一个新问题是NP难解的标准方法——若某个已证的NPC问题Π′能被归约为一个新问题Π（能采用新问题的条件和语汇来描述已知的NPC问题），那么新问题Π便具有在多项式时间内不可解的特性，即NP难解。基于这一方法，Idsardi（2006a）试图将一个已被证明是NPC問题的有向汉密尔顿路径（directed Hamiltonian path）问题归约为优选论的生成问题，以此证明后者是NP难解。
汉密尔顿路径指一个图中每个顶点只经过一次且不重复的路径，即一个有向图G=（V， A）中V
文章首先介绍有关计算复杂性的相关概念，然后针对优选论是否具有计算难解的问题，概述各方面的论点，最后对优选论的算法等其他相关问题进行概括和总结。优选论；计算复杂性H017A010808
优选论（Optimality Theory，简称OT）自20世纪90年代诞生开始就引起国内外研究者的广泛关注。在保留其核心理论框架的前提下，优选论经历了多次技术上的调整以解释更多的音系问题，并被拓展到音系以外的其他领域，如句法、语用等，可见其理论思想具有较强的活力，其操作模式具有开放性，因而至今仍然是语言学界的主流理论之一。但与此同时，20多年来，围绕优选论产生的各种质疑和争论也从未间断过，优选论在理论和应用上一直面临着不少挑战。其中，优选论所具有的独特的操作模式和计算方法引发了近年来在计算音系学领域中对于优选论计算复杂性（computational complexity）问题的热议。所涉及的问题包括：优选论中的生成问题是否属于NP难解问题？学习者如何习得计算量庞大的制约条件等级排列以及底层形式？等等。对此，Eisner（1997）和Isardi（2006a， b）等人试图论证优选论在计算上是不可解的（intractable）从而否定优选论的运行模式。Kornai（2006a， b），Tesar（1995），Heinz， et al（2009），Riggle（2009），Kager（1999），Prince and Smolensky（1993/2004）等人则从不同角度对之进行反驳，支持优选论。本文首先介绍有关计算复杂性的相关概念，然后概述来自双方的论点，进而对优选论的其他相关问题进行总结。
一、 有关计算性的相关概念
早在20世纪50年代末，Chomsky便将数学思想引入到语言学研究当中，将二者结合起来，形成一种形式语言学理论。这种形式语法具有算法（algorithms）的特点。换言之，语法作为一种生成句子的装置，很像数学中的“算法”过程（陆极致1990：171， 182183）。
所谓算法指的是一系列解决问题的清晰指令，是一个有限规则的有序集合，对于某类问题的初始输入，它能在有限时间内机械地逐步计算，在有限步骤后计算终止，获得一个输出结果。一个问题可以有多种算法。一个算法的优劣可以用时间复杂度（timecomplexity）和空间复杂度（spacecomplexity）来衡量，分别表示完成计算过程所需的总步数以及所用存贮的单元数（Mitkov 2003：178； Linz 2001：343344； 堵丁柱等 2002：17； 赵瑞清、孙宗智 1989： 5457； 张泽增 1989：4）。
时间复杂度关注的是当某个问题的规模扩大后，程序运行所需的时间增长得有多快。这里需要区分多项式（polynomial）时间算法和指数（exponential）时间算法。形如n2的多项式中，表示问题规模或大小（size）的参数n在底数位置；形如2n的指数时间算法中，n在指数位置，随着n的变大，它所需的计算时间以爆炸性的速率迅速增加。例如，在一台每秒做1亿次运算的计算机上，对于时间复杂度分别是n3和3n的算法来说，当n达到60时，它们所需的计算时间分别为2.16×10-3秒和1.3×1011世纪。显然，当n较大时，后者所需的时间是计算机无法承受的。
马秋武等：试析优选论的计算复杂性问题所谓问题，指的是从输入映射到其结果（即输出）的函数。设f为多项式函数，n为输入的长度，当且仅当该问题存在着能在f（n）步之内完成该函数的图灵机（Turing machine）时，这一问题便“在多项式时间内可计算”（Heins， et al 2009）。多项式时间算法（或称有效果算法）被认为是好的算法，计算机可以执行。有好的算法的问题是易解（tractable）的，属于P类问题，即在确定型图灵机上有多项式时间算法（实际可用的算法）。若一个问题找不到或尚未找到有效算法，则称为难解的（intractable），属于“非确定多项式算法（nondeterministic polynomialtime algorithm）”，简称为NP类问题。如果所有NP问题都能规约（reduce）到某一种问题，那么这种问题称为NP难解（NPhard）问题（张泽增 1989：138； 张立昂 1996：227228）。
二、 优选论的计算复杂性问题
1. 经典优选论的运算模式
优选论把语言形式看成是制约条件交互作用的结果。其语法体系包括三大部分：生成器（Generator）、制约条件集合（The Constraint Set）和评估器（Evaluator），通常分别简写为GEN，CON，EVAL。它的运算模式如下：生成器为某个输入项生成一系列可能的输出项，即候选项集合（candidate set）；然后，评估器根据CON所提供的制约条件等级体系排列筛选出最优的候选项，即最终的输出项。
较之传统的基于规则的音系分析方法，优选论在语言类型的问题上表现出了强大的解释力，但其代价是计算的复杂度增加了，难以进行人工计算。有人认为，生成器所具有的自由分析原则（freedom of analysis）会产生无限多的结构，而计算无限数量的候选项需要无限的时间（Kager 1999：25），这必然会导致不可计算，故优选论不能成为一个合理的言语产出或感知模型。Idsardi（2006a）结合了计算复杂性理论，试图论证经典优选论的生成问题属于NP难解问题。该篇文章引发了对优选论计算性问题的关注和热烈讨论。以下分别介绍Idsardi对优选论不可解的证明以及来自各方支持优选论的论点。
2. 优选论计算不可解的论证
Garey and Johnson （1979）提出了证明一个新问题是NP难解的标准方法——若某个已证的NPC问题Π′能被归约为一个新问题Π（能采用新问题的条件和语汇来描述已知的NPC问题），那么新问题Π便具有在多项式时间内不可解的特性，即NP难解。基于这一方法，Idsardi（2006a）试图将一个已被证明是NPC問题的有向汉密尔顿路径（directed Hamiltonian path）问题归约为优选论的生成问题，以此证明后者是NP难解。
汉密尔顿路径指一个图中每个顶点只经过一次且不重复的路径，即一个有向图G=（V， A）中V
