My question is focused on two points:
- Is the set of decision problems a proper subset of computational problems?
- Is the class NP defined only on decision problems, hence, for (1), a proper subset of general computational problems?
These two points are relevant to define NP-complete and hard classes: if (2) holds, can I than conclude that computational problems that are not proper decision problems (e.g TSP or Shortest Path) cannot be in NP (simply because not defined) and hence, not NP-complete?
Lastly, if (2) holds, I would never need to show that a computational problem is in NP when demonstratig its NP-hardness, is not it?
Thank you in advance for the answer and sorry for any imprecision.
The class NP only consists of decision problems by definition. There is a related class FNP that generalizes NP to any sort of output instead of just yes or no answers.
Decision problems are a proper subset of computational problems. Optimization problems like Traveling Salesman are easily converted to decision problems, however, so if you're being asked whether TSP is NP-complete then you're probably being asked about the decision problem variant of it.