Logic and computational complexity

逻辑和计算复杂性

• 批准号: 105666-2006
• 负责人: Urquhart, Alasdair
• 金额: $ 2.26万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=390951
• 关键词: Logic; computational; complexity

The main aim of the research is to understand why certain problems are difficult to solve using computers.  Typical of such problems are those in which a certain number of simple constraints must be satisfied, as in constructing schedules.  The characteristic feature of such problems (known by the technical name of NP-complete problems), is that a solution, if found, is easy to check, but deciding whether or not such a solution exists in the worst case requires an exponentially long time relative to the size of the input.   The principal aim of the theory of complexity theory is to decide whether or not such problems, that seem to require exponentially long computation times in the worst case, really do require such times. My own research aims to work towards showing that exponentially long times are in fact required in the worst case by proving lower bounds on the length of certain kinds of proofs.  Since a computation showing that a solution doesn't exist can be considered as a proof of a kind, lower bounds on the length of proofs show that certain kinds of algorithms (including the algorithms most often used in practice to solve such problems) cannot be efficient in the worst case.

研究的主要目的是了解为什么某些问题很难用计算机解决。这类问题的典型是那些必须满足一定数量的简单约束的问题，例如在编制时间表时。这类问题(称为NP完全问题)的特征特征是，如果找到解决方案，很容易检查，但在最坏的情况下决定是否存在这样的解决方案需要相对于输入大小的指数级长的时间。复杂性理论的主要目的是决定是否存在这样的问题，在最坏的情况下，这似乎需要指数级的长时间计算，但确实需要这样的时间。我自己的研究旨在通过证明某些类型的证明的长度的下界来证明在最坏的情况下实际上需要指数级的长时间。因为表明不存在解的计算可以被认为是一种证明，所以证明的长度的下界表明某些类型的算法(包括实践中最常用来解决这类问题的算法)在最坏的情况下不能有效。