Studies on Computational Complexity/Load as a Metric for the Economy Principles in the Theory of Generative Grammar

研究了计算复杂性理论和描述复杂性理论在计算机科学和离散数学中的应用的可能性，作为极简方案中经济原则的度量，这是当前转换生成语法传统的理论框架。为了测量人类语言中计算操作的复杂性，需要确定操作本身的性质，并且根据极简主义假设，必须将有问题的头对头的运动重新表述为头对规格的运动，这可以更好地覆盖已注意到的现象，但在原则方面无法解释。通过将所有移动操作减少到只有一个移动到指定位置，它可以被认为是Merge操作的一个种类。然后，反过来，我们可以开始考虑只使用两种类型的合并操作（内部合并和外部合并）的经济原则的计算复杂性。极简规划中的经济原理可以分为派生经济和具象经济两类，两者都可以理解为离散优化问题。一旦理解了这一点，衍生经济的问题就不再是文献中经常提到的局部与全局之间的非此即彼的问题，而是局部约束能否解决人类语言衍生系统的本质——全局优化问题。已经发现，对于衍生经济和表征经济，必须区分局部性的概念，并且与通常持有的观点相反，计算的一步“前瞻性”对人类语言至关重要。必须避免的是在计算中“展望未来”超过一步，这将不可避免地导致指数级的组合爆炸。

Possibilities are investigated of the application of the computational complexity theory and the descriptive complexity theory in computer science and discrete mathematics, as the metric for the economy principles in the Minimalist Program, the current theoretical framework in the tradition of transformational generative grammar.In order to measure the complexity of computational operations in human language, the nature of the operations itself needs to be determined, and the problematic head-to-head movement can be, and by the minimalist assumption, must be reformulated as head-to-spec movement, which yields better empirical coverage of phenomena noticed, but left unaccounted for in principled terms.By reducing all the movement operations to just one that moves to a specifier position, it can be considered to be a species of the Merge operation. Then, in turn, we can begin to consider the computational complexity of the economy principles that employ just the two types of the Merge operation, Internal Merge and External Merge.The economy principles in the Minimalist Program can be divided into two types, Derivational Economy and Representational Economy, both of which can be understood as discrete optimization problems. Once so understood, the issues of derivational economy become not of an either-or questions between local vs. global as often alluded in the literature, but rather whether local constraints can solve the global optimization problems, which is the nature of derivational system of human language.It has been found that the notion of locality must be distinguished for derivational economy and representational economy, and the computational one-step "look-ahead" is essential for human language, contra commonly held views. What must be avoided is "look-far-ahead" of more than one step in computation, which inevitably ends up with combinatorial explosion of exponential order.