Completeness - Computing

Computing

  • In algorithms, the notion of completeness refers to the ability of the algorithm to find a solution if one exists, and if not, to report that no solution is possible.
  • In computational complexity theory, a problem P is complete for a complexity class C, under a given type of reduction, if P is in C, and every problem in C reduces to P using that reduction.
    For example, each problem in the class NP-complete is complete for the class NP, under polynomial-time, many-one reduction.
  • In computing, a data-entry field can autocomplete the entered data based on the prefix typed into the field; that capability is known as autocompletion.
  • In software testing, completeness has for goal the functional verification of call graph (between software item) and control graph (inside each software item).
  • The concept of completeness is found in knowledge base theory.

Read more about this topic:  Completeness