◀ ▲ ▶Branches / Theoretical-computer-science / Computability / Example: Examples of Computational Problems

Example: Examples of Computational Problems

(related to Part: Computability)

The formal definition of problems can be better explained by some of the following examples:

Example 1

• Domain: Trees.
• Instance: A given tree $T$
• Question: What is the length of the longest path contained in $T$?
• Types of answers: natural numbers $\mathbb N$.

Example of a decision problem

• Domain: natural numbers $\mathbb N.$
• Instance: $n\in N$
• Question: Is $n$ an odd number.
• Types of answers: set of truth values $\mathbb B.$

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Lawler; Lenstra; Rinnooy Kan; Shmoys: "The Traveling Salesman Problem", Wiley-Interscience, 1985