Co-NP-complete
Encyclopedia
In complexity theory
, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that they are the ones most likely not to be in P
. 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
of an NP-complete
problem. There are some problems in both NP
and co-NP, however it is not known if the sets are equal, although inequality is thought more likely. See co-NP and NP-complete
for more details.
Fortune showed in 1979 that if any sparse language
is co-NP-complete (or even just co-NP-hard), then , a critical foundation for Mahaney's theorem.
C is co-NP-complete if it is in co-NP 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. As a consequence, if we had a polynomial time algorithm for C, we could solve all co-NP problems in polynomial time.
, 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
, which asks whether there exists at least one such assignment. Note that the tautology problem for positive Boolean formulae remains co-NP complete, even though the satisfiability problem is trivial, as every positive Boolean formula is satisfiable.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that they are the ones most likely not to be in P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
. 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
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement...
of an NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem. There are some problems in both NP
NP
-Locations:* NP postcode area, Newport, United Kingdom* NP, country code for Nepal ** .np, the country code top level domain for Nepal* NP, anabbreviation for Ngee Ann Polytechnic, Singapore...
and co-NP, however it is not known if the sets are equal, although inequality is thought more likely. See co-NP and NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
for more details.
Fortune showed in 1979 that if any sparse language
Sparse language
In computational complexity theory, a sparse language is a formal language such that the number of strings of length n in the language is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes...
is co-NP-complete (or even just co-NP-hard), then , a critical foundation for Mahaney's theorem.
Formal definition
A decision problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
C is co-NP-complete if it is in co-NP 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. As a consequence, if we had a polynomial time algorithm for C, we could solve all co-NP problems in polynomial time.
Example
One simple example of a co-NP-complete problem is tautologyTautology (logic)
In logic, a tautology is a formula which is true in every possible interpretation. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921; it had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternate sense...
, 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
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
, which asks whether there exists at least one such assignment. Note that the tautology problem for positive Boolean formulae remains co-NP complete, even though the satisfiability problem is trivial, as every positive Boolean formula is satisfiable.