馬秋武 吳力菡

文章首先介紹有關(guān)計算復(fù)雜性的相關(guān)概念，然后針對優(yōu)選論是否具有計算難解的問題，概述各方面的論點，最后對優(yōu)選論的算法等其他相關(guān)問題進行概括和總結(jié)。優(yōu)選論；計算復(fù)雜性H017A010808

優(yōu)選論（Optimality Theory，簡稱OT）自20世紀90年代誕生開始就引起國內(nèi)外研究者的廣泛關(guān)注。在保留其核心理論框架的前提下，優(yōu)選論經(jīng)歷了多次技術(shù)上的調(diào)整以解釋更多的音系問題，并被拓展到音系以外的其他領(lǐng)域，如句法、語用等，可見其理論思想具有較強的活力，其操作模式具有開放性，因而至今仍然是語言學界的主流理論之一。但與此同時，20多年來，圍繞優(yōu)選論產(chǎn)生的各種質(zhì)疑和爭論也從未間斷過，優(yōu)選論在理論和應(yīng)用上一直面臨著不少挑戰(zhàn)。其中，優(yōu)選論所具有的獨特的操作模式和計算方法引發(fā)了近年來在計算音系學領(lǐng)域中對于優(yōu)選論計算復(fù)雜性（computational complexity）問題的熱議。所涉及的問題包括：優(yōu)選論中的生成問題是否屬于NP難解問題？學習者如何習得計算量龐大的制約條件等級排列以及底層形式？等等。對此，Eisner（1997）和Isardi（2006a， b）等人試圖論證優(yōu)選論在計算上是不可解的（intractable）從而否定優(yōu)選論的運行模式。Kornai（2006a， b），Tesar（1995），Heinz， et al（2009），Riggle（2009），Kager（1999），Prince and Smolensky（1993/2004）等人則從不同角度對之進行反駁，支持優(yōu)選論。本文首先介紹有關(guān)計算復(fù)雜性的相關(guān)概念，然后概述來自雙方的論點，進而對優(yōu)選論的其他相關(guān)問題進行總結(jié)。

一、 有關(guān)計算性的相關(guān)概念

早在20世紀50年代末，Chomsky便將數(shù)學思想引入到語言學研究當中，將二者結(jié)合起來，形成一種形式語言學理論。這種形式語法具有算法（algorithms）的特點。換言之，語法作為一種生成句子的裝置，很像數(shù)學中的“算法”過程（陸極致1990：171， 182183）。

所謂算法指的是一系列解決問題的清晰指令，是一個有限規(guī)則的有序集合，對于某類問題的初始輸入，它能在有限時間內(nèi)機械地逐步計算，在有限步驟后計算終止，獲得一個輸出結(jié)果。一個問題可以有多種算法。一個算法的優(yōu)劣可以用時間復(fù)雜度（timecomplexity）和空間復(fù)雜度（spacecomplexity）來衡量，分別表示完成計算過程所需的總步數(shù)以及所用存貯的單元數(shù)（Mitkov 2003：178； Linz 2001：343344； 堵丁柱等 2002：17； 趙瑞清、孫宗智 1989： 5457； 張澤增 1989：4）。

時間復(fù)雜度關(guān)注的是當某個問題的規(guī)模擴大后，程序運行所需的時間增長得有多快。這里需要區(qū)分多項式（polynomial）時間算法和指數(shù)（exponential）時間算法。形如n2的多項式中，表示問題規(guī)?；虼笮。╯ize）的參數(shù)n在底數(shù)位置；形如2n的指數(shù)時間算法中，n在指數(shù)位置，隨著n的變大，它所需的計算時間以爆炸性的速率迅速增加。例如，在一臺每秒做1億次運算的計算機上，對于時間復(fù)雜度分別是n3和3n的算法來說，當n達到60時，它們所需的計算時間分別為2.16×10-3秒和1.3×1011世紀。顯然，當n較大時，后者所需的時間是計算機無法承受的。

馬秋武等：試析優(yōu)選論的計算復(fù)雜性問題所謂問題，指的是從輸入映射到其結(jié)果（即輸出）的函數(shù)。設(shè)f為多項式函數(shù)，n為輸入的長度，當且僅當該問題存在著能在f（n）步之內(nèi)完成該函數(shù)的圖靈機（Turing machine）時，這一問題便“在多項式時間內(nèi)可計算”（Heins， et al 2009）。多項式時間算法（或稱有效果算法）被認為是好的算法，計算機可以執(zhí)行。有好的算法的問題是易解（tractable）的，屬于P類問題，即在確定型圖靈機上有多項式時間算法（實際可用的算法）。若一個問題找不到或尚未找到有效算法，則稱為難解的（intractable），屬于“非確定多項式算法（nondeterministic polynomialtime algorithm）”，簡稱為NP類問題。如果所有NP問題都能規(guī)約（reduce）到某一種問題，那么這種問題稱為NP難解（NPhard）問題（張澤增 1989：138； 張立昂 1996：227228）。

二、 優(yōu)選論的計算復(fù)雜性問題

1. 經(jīng)典優(yōu)選論的運算模式

優(yōu)選論把語言形式看成是制約條件交互作用的結(jié)果。其語法體系包括三大部分：生成器（Generator）、制約條件集合（The Constraint Set）和評估器（Evaluator），通常分別簡寫為GEN，CON，EVAL。它的運算模式如下：生成器為某個輸入項生成一系列可能的輸出項，即候選項集合（candidate set）；然后，評估器根據(jù)CON所提供的制約條件等級體系排列篩選出最優(yōu)的候選項，即最終的輸出項。

較之傳統(tǒng)的基于規(guī)則的音系分析方法，優(yōu)選論在語言類型的問題上表現(xiàn)出了強大的解釋力，但其代價是計算的復(fù)雜度增加了，難以進行人工計算。有人認為，生成器所具有的自由分析原則（freedom of analysis）會產(chǎn)生無限多的結(jié)構(gòu)，而計算無限數(shù)量的候選項需要無限的時間（Kager 1999：25），這必然會導(dǎo)致不可計算，故優(yōu)選論不能成為一個合理的言語產(chǎn)出或感知模型。Idsardi（2006a）結(jié)合了計算復(fù)雜性理論，試圖論證經(jīng)典優(yōu)選論的生成問題屬于NP難解問題。該篇文章引發(fā)了對優(yōu)選論計算性問題的關(guān)注和熱烈討論。以下分別介紹Idsardi對優(yōu)選論不可解的證明以及來自各方支持優(yōu)選論的論點。

2. 優(yōu)選論計算不可解的論證

Garey and Johnson （1979）提出了證明一個新問題是NP難解的標準方法——若某個已證的NPC問題Π′能被歸約為一個新問題Π（能采用新問題的條件和語匯來描述已知的NPC問題），那么新問題Π便具有在多項式時間內(nèi)不可解的特性，即NP難解?；谶@一方法，Idsardi（2006a）試圖將一個已被證明是NPC問題的有向漢密爾頓路徑（directed Hamiltonian path）問題歸約為優(yōu)選論的生成問題，以此證明后者是NP難解。

漢密爾頓路徑指一個圖中每個頂點只經(jīng)過一次且不重復(fù)的路徑，即一個有向圖G=（V， A）中V