In
complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in
co-NP
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 is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If
P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly.
Each co-NP-complete problem is the
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
of an
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
problem. There are some problems in both
NP and
co-NP
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 is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
, for example all problems in
P or
integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
. However, it is not known if the sets are equal, although inequality is thought more likely. See
co-NP
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 is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
and
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
for more details.
Fortune showed in 1979 that if any
sparse language In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length ''n'' in the language, is bounded by a polynomial function of ''n''. They are ...
is co-NP-complete (or even just co-NP-hard), then ,
a critical foundation for
Mahaney's theorem Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-complete, then P = NP. Also, if any sparse language is NP-complete with respect to Turing reduction
In computa ...
.
Formal definition
A
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
''C'' is co-NP-complete if it is in
co-NP
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 is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
and if every problem in co-NP is
polynomial-time many-one reducible to it.
This means that for every co-NP problem ''L'', there exists a polynomial time algorithm which can transform any instance of ''L'' into an instance of ''C'' with the same
truth value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false'').
Computing
In some progr ...
. As a consequence, if we had a polynomial time algorithm for ''C'', we could solve all co-NP problems in polynomial time.
Example
One example of a co-NP-complete problem is
tautology, the problem of determining whether a given
Boolean formula is a tautology; that is, whether every possible assignment of true/false values to variables yields a true statement. This is closely related to the
Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
, which asks whether there exists ''at least one'' such assignment, and is NP-complete.
References
External links
*
{{ComplexityClasses
Complexity classes