I am interested in all know classes of Computatinal problems. The Wikipedia article on computational problems types is incomplete. Some of the known classes are:

1- Decision problem such as 3SAT

2- Search problem such Factoring search problem

3- Function problem such as finding a second Hamiltonian cycle on a cubic graph (given some Hamiltonian cycle) which in TFNP

4- Optimization problem such as maximum independent set problem

5- Uniqueness problem such as Unique SAT problem

6- Another solution problem such as finding a second Hamiltonian cycle on a general graph (given some Hamiltonian cycle) which is in NP

7- Counting problem such as counting perfect matchings in bipartite graphs

8- Promise problem such as finding solution of SAT under the promise that it has a unique solution

9- Inverse problem such as Inverse 3SAT

10- Extendibility problem such as edge precoloring extension problem on bipartite graphs

11- Parity problem such as Parity-SAT

What other types of computational problems should be added to the above list?

P.S. Some of the above can be cast as decision problem such as optimization problems.

  • 1
    $\begingroup$ This looks too broad to me. Any community votes? $\endgroup$ – D.W. Jun 14 '18 at 7:43
  • 1
    $\begingroup$ And too list-y. $\endgroup$ – David Richerby Jun 14 '18 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.