BEGIN:VCALENDAR VERSION:2.0 PRODID:ILLC Website X-WR-TIMEZONE:Europe/Amsterdam BEGIN:VTIMEZONE TZID:Europe/Amsterdam X-LIC-LOCATION:Europe/Amsterdam BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:19700329T020000 RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:19701025T030000 RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:/NewsandEvents/Archives/2008/newsitem/2551/26- November-2008-Logic-Language-and-Reasoning-Seminar -Iris-van-Rooij-Radbout-University-Nijmegen- DTSTAMP:20081009T000000 SUMMARY:Logic, Language and Reasoning Seminar, Iri s van Rooij (Radbout University Nijmegen) ATTENDEE;ROLE=Speaker:Iris van Rooij (Radbout Univ ersity Nijmegen) DTSTART;TZID=Europe/Amsterdam:20081126T150000 DTEND;TZID=Europe/Amsterdam:20081126T170000 LOCATION:Room 3.27, ILLC, Plantage Muidergracht 24 , Amsterdam DESCRIPTION:Abstract: There are many ways in whic h a problem can be hard or easy. In this talk I wi ll 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 impor tant role in debates in cognitive science over the last decades, among them debates on the modularit y of mind and the heuristic nature of human ration ality. In these debates often claims have been mad e (explicitly or implicitly) about what it is that makes a given problem hard. Reasons that are comm only listed include the following: (1) optimizatio n 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) satisf icing is relatively easy, (5) heuristics are relat ively easy, and (6) approximation is relatively ea sy. In this talk I discuss the misleading nature o f these claims. Drawing on insights from complexit y theory, I propose an alternative way of addressi ng the question "What makes a problem hard (or eas y)?", one that recognizes that the hardness or eas iness of a problem often depends on a complex inte rplay of a problem's parameters. For more infor mation, see http://staff.science.uva.nl/~szymanik/ LLR.html X-ALT-DESC;FMTTYPE=text/html:\n
\n
Abstract:
\n There are many ways in wh
ich 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 ar
e traditionally considered to be hard in this sens
e. This notion of hardness has been playing an imp
ortant role in debates in cognitive science over t
he last decades, among them debates on the modular
ity of mind and the heuristic nature of human rati
onality. In these debates often claims have been m
ade (explicitly or implicitly) about what it is th
at makes a given problem hard. Reasons that are co
mmonly listed include the following: (1) optimizat
ion 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 wha
t characterizes easy problems, including: (4) sati
sficing is relatively easy, (5) heuristics are rel
atively easy, and (6) approximation is relatively
easy. In this talk I discuss the misleading nature
of these claims. Drawing on insights from complex
ity theory, I propose an alternative way of addres
sing the question "What makes a problem hard
(or easy)?", one that recognizes that the har
dness or easiness of a problem often depends on a
complex interplay of a problem's parameters.\n
\n For more informat ion, see\n http://st aff.science.uva.nl/~szymanik/LLR.html\n < /p> URL:/NewsandEvents/Archives/2008/newsitem/2551/26- November-2008-Logic-Language-and-Reasoning-Seminar -Iris-van-Rooij-Radbout-University-Nijmegen- END:VEVENT END:VCALENDAR