3
$\begingroup$

A computational problem consists of a set of instances. In most cases the set of instances is infinite. Like the set of all graphs, e.g.:

Given a graph $G$, is there a Hamiltonian circuit in $G$?

Can the set of instances be finite and a problem still be non-trivial?

$\endgroup$
0
5
$\begingroup$

A finite problem can be decided in O(1) time: we can simply compare the input to a finite (bounded) list of known cases, and emit the output consequently.

Indeed, for that we do not need a Turing powerful system: a finite-state automaton suffices.

So, the problem is indeed trivial.

Co-finite (finite complement) problems are similarly trivial.

$\endgroup$
3
$\begingroup$

Depends on your definition of "trivial". The finite number of instances of a finite problem may be so large that the problem isn't solvable at all in practice. For example, determine the best possible move for every legal chess position...

But of course, you can create a somehow sorted table of all possible instances and their solutions, and then binary search in that table will find the solution of any problem quite quickly and trivially. Except the table may just be too big to create.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.