The class NP
A decision problem of the form “there exists an object J
such that for the given input I property(I,J) holds”
is in the class NP if there is an algorithm that for any
given input I and given object J determines whether
property(I,J) holds and has worst-case running time of
O(na) for a fixed a, where n is the size of the input. Note
that the decision problem corresponding to the multiple
sequence alignment problem is in the class NP.