Skip to main content
1 of 2

Decision problems vs functions

Complexity theory seems to be built around decision problems rather than functions. Who introduced this first and what is the reason for this choice? For example, Edmonds "Paths, trees and flowers" is generally credited as the source of the notion of PTIME representing the set of "tractable" problems and this is the path that we have taken.