Rudolf Adamkovič Personal site

Up: Index of computer science   [Top][Contents]

Decision problem

A computational problem whose

every instance is answered with a Boolean value.

For example, SAT but not TSP. 4

Footnotes

(4)

TSP can be converted to a decision problem by asking

Is there a tour with a cost less than \(c\)?

for some constant \(c\).

© 2024 Rudolf Adamkovič under GNU General Public License version 3.
Made with Emacs and the secret alien technologies of yesteryear.