Back كو-إن بي Arabic Co-NP (Complexitat) Catalan Co-NP German Co-NP Spanish Co-NP French Co-NP HE Co-NP Italian Co-NP Japanese Co-NP Korean Klasa Co-NP Polish
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and only if for every no-instance we have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.
That is, co-NP is the set of decision problems where there exists a polynomial and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by , the Turing machine M accepts the pair (x, c).[1]
- ^ Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. p. 56. ISBN 978-0-521-42426-4.