Sources of complexity in subset choice

摘要

Subset choice denotes the task of choosing a subset of items from among a set of available items. Because the number of possible choice options in subset choice grows exponentially with the size of the choice set, subset choice tasks can be computationaily challenging. This paper discusses how the computational complexity of subset choice under different models can be utilized in the quest for descriptive models of subset choice. We consider several models of subset choice (including the additive model, the binary-interaction model and the h-ary interaction model) and show how the theory of computational complexity (including the theory of NP-completeness and fixed-parameter tractability) can be used to evaluate the psychological plausibility of such models under different assumptions of processing speed, parallelism and size of problem parameters. 2005 Elsevier Inc. All rights reserved.