Skip to main content
Theoretical Computer Science

Return to Question

edited tags; edited tags
Source Link
Kaveh
Kaveh
  • 21.8k
  • 8
  • 84
  • 185

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, EdmondsEdmonds' "Paths, trees and flowers" paper is generally credited as the source of the notion of PTIME$\mathsf{PTime}$ representing the set of "tractable" problems and this is the path that we have taken.

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.

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" paper is generally credited as the source of the notion of $\mathsf{PTime}$ representing the set of "tractable" problems and this is the path that we have taken.

Tweeted twitter.com/#!/StackCSTheory/status/337523436832301057
Source Link
Thinniyam Srinivasan Ramanatha
Thinniyam Srinivasan Ramanatha
  • 259
  • 1
  • 5

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.