Parameterized complexity analysis in cognitive science

点击翻译按钮获取中文摘要

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.