Optimization problem: Difference between revisions

Revision as of 19:07, 21 May 2018

Revision as of 00:40, 18 June 2018

Line 55:

| isbn = 978-3-540-44134-2

}}</ref> Note that the below referred [[Polynomial|polynomials]] are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances.

* the size of every feasible solution <math>\scriptstyle y\in f(x)</math> is polynomially [[Bounded set|bounded]] in the size of the given instance <math>x</math>,

* the languages <math>\scriptstyle \{\,x\,\mid\, x \in I \,\}</math> and <math>\scriptstyle \{\,(x,y)\, \mid\, y \in f(x) \,\}</math> can be [[decidable language|recognized]] in [[polynomial time]], and

* ''m'' is [[polynomial time|polynomial-time computable]].