Difficulty and completeness (theoretical computer science)

In theoretical computer science - especially in the computability and complexity theory - indicates the severity (Translation of English. Hardness dt. "Difficulty" ) of a problem whose property, at least to be as difficult as solved all the problems of a class under consideration. The completeness of a problem then means that it is one of the most difficult problems in this class. To put it clearly, an algorithm that is difficult Problem can solve all problems of the corresponding class with only minor modifications.

The idea of ​​comparing problems according to their solvability and thereby investigating difficult and complete problems goes back to an article by Emil Post from 1944.

Definitions

Severity and completeness are usually only considered for decision problems . With these, the question is asked whether a certain object has a special property or not. More precisely, it is even sufficient - through a suitable godelization - to consider only decision problems of sets of natural numbers . The goal is always to calculate the characteristic function of a subset of . This approach has the advantage that the problems with the subsets themselves can now be identified. However, it is very easy to apply the following definitions to optimization and search problems . ${\displaystyle \mathbb {N} }$

So let us now be a set system over the natural numbers, another set and finally a (computability or complexity theory) reduction . ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle \preceq }$

• The problem is called -difficult with respect to if: ${\displaystyle A}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \preceq }$ ${\displaystyle \forall C\in {\mathcal {C}}\colon C\preceq A}$

So if every problem in the class can be reduced to -. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle A}$ ${\displaystyle \preceq }$

• ${\displaystyle A}$hot -complete with regard to if additionally itself is in . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \preceq }$ ${\displaystyle A}$ ${\displaystyle {\mathcal {C}}}$

If there is a complexity class , then usually only those reductions are considered whose computational effort is still within the class itself. ${\displaystyle {\mathcal {C}}}$

Way of speaking

If it is clear or irrelevant from the context which reduction is involved, this is often left out in the notation. For example, the term NP-completeness means that a problem is complete for the complexity class of all problems that can be non-deterministically solvable in polynomial time with regard to the polynomial time-restricted or the logarithmically space-restricted many-one reduction . This abbreviation is possible because in this special case the two types of reduction are equivalent.

The indication of the considered class of problems is sometimes even suppressed, as it is mainly in the English language completely (English complete ) for the property of a problem completely for the class of recursively enumerable amounts with respect to the many-one or one-one-reduction to be. Here, too, the two reductions considered are equivalent.

Examples

• Stephen Cook showed in 1971 that the satisfiability problem of propositional logic is NP-complete, and one year later Richard Karp demonstrated this property for 20 other problems . ${\displaystyle SAT}$
• Conversely, problem classes can also be defined by specifying a problem that is complete for them (with regard to a specific reduction). The complexity class NP is the totality of all problems that can be reduced to polynomial time-limited many-one to . ${\displaystyle SAT}$
• A set can be recursively enumerated if and only if it can be reduced many-one to the holding problem . itself is also in RE , which is why it is RE-complete. ${\displaystyle H}$ ${\displaystyle H}$
• Since the special halting problem and the -Halteproblem isomorphic recursively to , they are also RE-complete. ${\displaystyle K}$ ${\displaystyle \varepsilon }$ ${\displaystyle H_{0}}$ ${\displaystyle H}$
• Both the set of all total calculable functions and their complement are RE-difficult but not RE-complete. ${\displaystyle TOTAL}$

properties

• The reductions form quasi-orders on the set of all problems. The severities problems are then just the upper bounds and the -vollständigen problems the maxima of the class with respect . It should be noted that due to the lack of antisymmetry of the maxima do not necessarily have to be unique. ${\displaystyle \preceq }$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \preceq }$ ${\displaystyle \preceq }$
  • In particular, reductions are transitive . So if a problem is difficult for the class and also applies to another problem, then this is also -hard. ${\displaystyle A}$ ${\displaystyle \preceq }$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle A\preceq B}$ ${\displaystyle {\mathcal {C}}}$
• A lot is productive if and only if it is coRE-heavy, this is Myhill's theorem . The computability class coRE contains the complements of recursively enumerable sets.
  • It follows that the creative sets are exactly RE-complete.
• In general, the behavior of complementary classes or problems depends on the chosen reduction:
  • Under the Turing reduction , for example, a problem is -difficult when it is -difficult. ${\displaystyle \preceq _{T}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle co{\mathcal {C}}}$
  • Under the many-one reduction, on the other hand, a problem is - severe if and only if its complement is - severe. ${\displaystyle \preceq _{m}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle co{\mathcal {C}}}$

See also

• NP severity
• NP completeness

Individual evidence

1. ↑ E. Post: Recursively enumerable sets of positive integers and Their decision problems. Bulletin of the American Mathematical Society, vol. 50 (1944), no.5, pp. 284 ?? 316 (online, PDF file; 4.0 MB)
2. ^ H. Rogers jr .: Theory of recursive functions and effective computability. 2nd ed., 3rd printing (1992), MIT Press, Cambridge MA, ISBN 0-262-68052-1 - §7.5 Theorem VII, p. 87
3. ^ J. Myhill: Creative sets . In: Journal for Mathematical Logic and Fundamentals of Mathematics Ed. 1 (1955), pp. 97-108