Rudolf Adamkovič Personal site

Up: Computer science   [Top][Contents]

Decision problem

A computational problem whose

every instance is answered with a Boolean value.

For example, SAT but not TSP. 5

Footnotes

(5)

TSP can be converted to a decision problem by asking

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

for some constant \(c\).

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