Rudolf Adamkovič Personal site

Up: Personal website   [Top][Contents]

Decision problem

A computational problem whose

every instance is answered with a Boolean value.

For example, SAT but not TSP. 1

Footnotes

(1)

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.