Parameterized complexity analysis in cognitive science

作为人类，我们每天都在不断地进行计算，这是我们日常生活的一部分--我们在杂乱的桌子上寻找放错了钥匙的地方，我们计划去一系列商店购买即将到来的派对所需的一切，我们决定将邻居的孩子比作一头逃跑的公牛是(或不是)合适的。我们快速且(在很大程度上)正确地进行这些计算，它们看起来如此简单--然而，经过50年的研究，计算机科学的一个分支--人工智能(AI)--尚未在机器人和软件系统中复制许多我们认为是理所当然的人类认知能力。这不仅仅是一个软件或硬件的问题--在认知科学领域工作的心理学家在推导一般理论方面同样困难，这些理论解释了我们如何像做事情一样快、一样好地做事情。

Every day, we as human beings are constantly performing computations as part of our everyday lives -- we search cluttered desks for misplaced keys, we make plans for visiting a set of stores to get everything we need for an upcoming party, we decide that comparing a neighbor's child to a runaway bull is (or is not) appropriate. We do these computations quickly and (for the most part) correctly, and they seem so simple -- however, after 50 years of research, the subdiscipline of Computer Science called Artificial Intelligence (AI) has yet to replicate in robots and software systems many human cognitive abilities that we take for granted. This is not just a software or hardware problem -- psychologists working in Cognitive Science have equal difficulties deriving general theories explaining how we do the things we do as quickly and as well as we do.