Sources of complexity in subset choice

I. Rooij, van, U. Stege, H. Kadlec

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)
3 Downloads (Pure)


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 computationally 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.
Original languageEnglish
Pages (from-to)160-187
JournalJournal of Mathematical Psychology
Issue number2
Publication statusPublished - 2005


Dive into the research topics of 'Sources of complexity in subset choice'. Together they form a unique fingerprint.

Cite this