Logic and computational complexity

逻辑和计算复杂性

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

The principal aim of my research is to understand the limitations of computer programs in solving certain important types of problems. These problems are ones where there are a certain number of conditions to be satisfied; assuming a given collection of conditions, it is easy to check whether or not a proposed solution is in fact correct, but it appears to be difficult to search for a solution. An everyday example of this kind of problem is provided by puzzles, such as jigsaw puzzles, or the problem of solving Rubik's Cube. These type of problems are in the category NP. Of these, the best known is the Satisfiability problem from logic, which is the problem of whether a formula of propositional logic has a satisfying assignment.

我研究的主要目的是了解计算机程序在解决某些重要问题方面的局限性。这些问题需要满足一定数量的条件；假设有一组给定的条件，很容易检查所提出的解决方案实际上是否正确，但寻找解决方案似乎很困难。这类问题的一个日常例子是拼图游戏，如拼图游戏或解决魔方的问题。这类问题属于NP范畴。其中，最著名的是逻辑学中的可满足性问题，即命题逻辑的公式是否具有令人满意的赋值。