NotesFAQContact Us
Search Tips
Peer reviewed Peer reviewed
Direct linkDirect link
ERIC Number: EJ1174094
Record Type: Journal
Publication Date: 2018-Jan
Pages: 19
Abstractor: As Provided
ISSN: EISSN-1932-6246
The Role of the Goal in Solving Hard Computational Problems: Do People Really Optimize?
Carruthers, Sarah; Stege, Ulrike; Masson, Michael E. J.
Journal of Problem Solving, v11 n1 Article 1 Jan 2018
The role that the mental, or internal, representation plays when people are solving hard computational problems has largely been overlooked to date, despite the reality that this internal representation drives problem solving. In this work we investigate how performance on versions of two hard computational problems differs based on what internal representations can be generated. Our findings suggest that problem solving performance depends not only on the objective difficulty of the problem, and of course the particular problem instance at hand, but also on how feasible it is to encode the goal of the given problem. A further implication of these findings is that previous human performance studies using NP-hard problems may have, surprisingly, underestimated human performance on instances of problems of this class. We suggest ways to meaningfully frame human performance results on instances of computationally hard problems in terms of these problems' computational complexity, and present a novel framework for interpreting results on problems of this type. The framework takes into account the limitations of the human cognitive system, in particular as it applies to the generation of internal representations of problems of this class.
Purdue University Press. Stewart Center Room 370, 504 West State Street, West Lafayette, IN 47907. Tel: 800-247-6553; Fax: 419-281-6883; e-mail: pupress@purdue,edu; Web site:
Publication Type: Journal Articles; Reports - Research
Education Level: Higher Education; Postsecondary Education
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A
Identifiers - Location: Canada (Victoria)
Grant or Contract Numbers: N/A