Types of computational problems

This is not an exhaustive list because there are likely other kinds of problems or some esoteric concepts I may have forgot.

The list below:

• CSPs (Constraint Satisfiability Problems). This can also include DCSPs (Dynamic Constraint Satisfiability Problems) and many other variants of this category of problem.
• Function Problems.
• Decision Problems.
• Optimization Problems.
• Search Problems.
• Counting Problems.

Some discussion:

The CSPs: we already know is equivalent to conjunctive query containment problems. In shorthand CSP = CQCP.

We know CSPs can have variants, like DCSP, WCSP, etc. I will not go into every possible variant because all we really need to know is that CSP is the main category which all these variants fall under.

Function Problems: are Functional Boolean Satisfiability Problems. This problem category I do not know a whole lot about but a single output is expected for every input.

Decision problems: Now these other problems above are categories but the next list of problems are even more fundamental. For example decision problems collapse logically into true or false, yes or no, 1 or 0. So if you give a query, you are hoping to get a "decision" between option A or option B, and this is a decision problem. Decidability is important to note here because it is decidability which allows for the collapse to happen. An undecidable problem is a problem which no matter what algorithm you use to receive the input it will never reach a yes or no, or a true or false, or a 1 or 0, because it's undecidable (example is the halting problem). We know also decision problems are related to formal languages (every decision problem can be defined by a formal language because problems = languages) so DPs = CFGs (context free grammars).

Optimization problems: These kinds of problems are solved by finding the best solution from all feasible options. The feasibility region or solution space is important as a concept to understand this kind of problem. This is essentially a search problem and the goal is to search the solution space for the solution which best fits the desired criteria. The sorts of algorithms we see to solve these are bee pollination algorithms, or ant colony optimization algorithms, or simulated annealing.

Search problems: These are among the most fundamental of all problem types. The ability to search for any solution to any problem is a search problem in itself. A search problem is defined by having a set of states, a start state, a goal state, a boolean function telling whether a given state is a goal state, a successor function, a mapping from a state to a set of new states.

A set of states
A start state
A goal state or goal test
A boolean function which tells us whether a given state is a goal state
A successor function
a mapping from a state to a set of new states

If you have the problem of knowing what a solution looks like, and you can provide a specification for this, but you do not know what algorithm would give you this, you essentially are dealing with a search problem. I would say for example optimization problems at the core are search problems because you search through a solution space (feasibility region), and any problem in general requires knowledge search, which is the process of searching for the necessary knowledge to even approach solving the problem.

Counting Problems: These are fundamental problems involving complexity. I will admit I do not know the details of these problems yet to speak much on them but the goal of it it is to find the number of elements in a finite set of objects.

Conclusion

As we can see, when we can recognize different problems and classify them we can then know a bit more about when to apply what. For example if we look at what developers are doing such as if they are focused on a certain theoretical area (decidability) for example then we know that it's important because it allows for the solving of certain kinds of problems where you have an input to an algorithm which can always deliver a yes or a no. For anything involving logic this kind of decidability is going to be critical if you want to be able to handle certain kinds of application of that logic.

We can also see an example of a pattern match or in this case exact match between CSP and CQCP. This is the result of a paper "Conjunctive-query containment and constraint satisfaction" from Vardi, Kolatis, et al (2000).

We can also connect dots and see that to solve certain kinds of problem requires more fundamental solutions, so to optimize you must search, to solve CSP you must search, etc. So when you think of something like software synthesis from a specification you know it's search at the most fundamental level but when you think about optimization you also know that is search at a fundamental level. When you understand this you can ask deeper questions like what happens when you combine a numerical solver with a SAT solver (Numerical Solver + SAT Solver = ?). And if you ask a question like that you could find: "ReaS: Combining Numerical Optimization with SAT Solving" by Inala, Gao, eta al,. (2018).

The take away is the more you understand theoretical computer science, the types of computational problems, the similarities between different problems within the same domain (computer science), then you can begin to ask deeper questions, and refine your knowledge search or your queries. In general, to solve a decision problem is to solve a whole category of problems which fall under "decision problems", and to solve an optimization problem is to solve a whole category of problems which fall under "optimization", and so on, and in any application or engineering project there is going to be a phase involving optimization, a phase involving some of these elements from other kinds of problems, which if you solved it in the past in a particular kind of way or you are just aware of a very elegant solution for example to the whole class of problem then you can look up your own previous solution or your approaches.

Example you might find that you did all the calculations involving computational complexity, involving the comp sci theory, to the point where you developed an approach to solve some unrelated problem in the distant past. Now you are doing something new, an entirely new project, and you realize now you have the exact same problem once again, an optimization problem, or a decision problem or a search problem, and you know from the past certain algorithms you applied can do this or it can't do that. For example binary decision diagrams as a data structure is known to be able to do certain things very well, but not everything well, but if you worked with BDDs in the past you would have learned their strengths, their limitations, and you will now know when to apply the BDD data structure to future problems you encounter (decision problems).

References

1. https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
2. https://en.m.wikipedia.org/wiki/Function_problem
3. https://en.m.wikipedia.org/wiki/Decision_problem
4. https://en.wikipedia.org/wiki/Undecidable_problem
5. https://en.wikipedia.org/wiki/Search_problem
6. https://en.wikipedia.org/wiki/Computational_problem
7. https://en.wikipedia.org/wiki/Mathematical_optimization

Kolaitis, Phokion G., and Moshe Y. Vardi. "Conjunctive-query containment and constraint satisfaction." Journal of Computer and System Sciences 61.2 (2000): 302-332.

Inala, J. P., Gao, S., Kong, S., & Solar-Lezama, A. (2018). REAS: Combining Numerical Optimization with SAT Solving. arXiv preprint arXiv:1802.04408.