Content deleted Content added
→NP optimization problems: clarification |
|||
Line 33:
| isbn = 978-3540441342
}}</ref> Note that the below referred 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 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]].
| |||