Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

26 November 2008, Logic, Language and Reasoning Seminar, Iris van Rooij (Radbout University Nijmegen)

Speaker: Iris van Rooij (Radbout University Nijmegen)
Title: What Makes a Problem Hard (or Easy)? A Computational Perspective
Date: Wednesday 26 November 2008
Time: 15:00-17:00
Location: Room 3.27, ILLC, Plantage Muidergracht 24, Amsterdam

Abstract:
There are many ways in which a problem can be hard or easy. In this talk I will focus on one such meaning: a problem is hard if solving it requires an excessive amount of time. NP-complete - or otherwise NP-hard - problems are traditionally considered to be hard in this sense. This notion of hardness has been playing an important role in debates in cognitive science over the last decades, among them debates on the modularity of mind and the heuristic nature of human rationality. In these debates often claims have been made (explicitly or implicitly) about what it is that makes a given problem hard. Reasons that are commonly listed include the following: (1) optimization is hard, (2) solving a problem exactly is hard, (3) problems with large search spaces are hard. On the other hand, there are also claims about what characterizes easy problems, including: (4) satisficing is relatively easy, (5) heuristics are relatively easy, and (6) approximation is relatively easy. In this talk I discuss the misleading nature of these claims. Drawing on insights from complexity theory, I propose an alternative way of addressing the question "What makes a problem hard (or easy)?", one that recognizes that the hardness or easiness of a problem often depends on a complex interplay of a problem's parameters.

For more information, see http://staff.science.uva.nl/~szymanik/LLR.html

Please note that this newsitem has been archived, and may contain outdated information or links.