Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Limits? What Limits? Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

20. Complete Problems

verfasst von : Bernhard Reus

Erschienen in: Limits of Computation

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this chapter we consider various examples of NP-complete problems. A famous result by Cook and Levin will provide us with a very first NP-complete problem. To this problem one can then apply reduction to show that other problems are NP-hard as well. Several such NP-complete problems are introduced: reachability of a (favourable) position for many interesting games, (unrestricted) database queries, and policy based routing. It turns out that most optimisation problems that are not in P are NP-complete. But there are also so-called NP-intermediate problems, for which we do not know whether they are NP-complete nor whether they are in P. Finally, will briefly discuss the concept of completeness for other complexity classes, i.e. P and semi-decidable problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel How Hard Is a Problem?
Nächstes Kapitel How to Solve NP-Complete Problems
Fußnoten
1
There are so-called “truth tables” for each Boolean operator that fully explain its semantics.
 
2
This version of the problem is also sometimes called CNFSAT, when SAT is used to denote the problem for unrestricted propositional formulae.
 
3
The actual number of different variables is then less than or equal n.
 
4
Leonid Levin (born November 2, 1948) is a Soviet-American computer scientist who has apparently proved the same theorem as Stephen Cook independently behind the (then still existing) “iron curtain”.
 
5
A more detailed proof can be found in many textbooks.
 
6
There are many examples of this: consider Max-Cut versus Min-Cut or Integer Programming versus Linear Programming, TSP versus Postman Problem, and so on.
 
7
Recall that a consequence of this is that if any of those problems were in P we could deduce P = NP.
 
8
Karp [16] actually showed SAT \(\le _P\) Clique \(\le _P\) Node Cover \(\le _P\) Directed Hamiltonian Circuit \(\le _P\) Undirected Hamiltonian Circuit.
 
9
Karp [16] named this problem “Chromatic Number”.
 
10
Karp [16] actually showed that Graph Colouring \(\le _P\) Exact Cover \(\le _P\) 0-1Knapsack.
 
11
Karp [16] actually showed that 0-1 Knapsack \(\le _P\) Partition \(\le _P\) Max-Cut.
 
12
[14, Chap. 25.6].
 
13
Bejeweled TM is a trademark of PopCap Games and Candy Crush TM is a trademark of King.com Ltd.
 
14
Non-chess players are encouraged to look them up and play this classic game.
 
15
Without the 50 move rule that says that if no pawn was moved and no piece captured in the last 50 moves then it’s a draw.
 
16
Of course, not all these positions are legal positions but this can be ignored for this approximation.
 
17
In conclusion, [27] raises another interesting question: Since hundreds of millions of hours globally are spent playing Candy CrushTM and similar games, could one profit from this by using the manpower to solve other NP-complete problems hidden in the games?
 
18
Moshe Ya’akov Vardi is an Israeli computer scientist who teaches at Rice University in the US. His research spans many fields of computer science, including database systems, complexity theory, and program specification and verification. He has won numerous awards.
 
19
In a relational database system there is an optimizer which tries to avoid exactly this. And of course, real-life queries are—most of the time—not very large.
 
20
i.e. returning the same result as the original query.
 
21
So \(\mathcal{P}((u,v),p)\) can be interpreted as the set of rules of network device (router) u for destination v depending on the packet p to be forwarded. Usually, only (parts of) the header of packet p is considered, but not its payload.
 
22
We won’t go into the details of Classless Inter-Domain Routing (CIDR) address notation taught in every Network course.
 
23
This protocol still routes most traffic today despite the advent of IPv6.
 
24
Limbo denotes an uncertain period of awaiting a decision or resolution. The name origins in theology where it refers to a certain part of “hell” but is now used generally in the aforementioned sense.
 
25
László Babai (born July 20, 1950) is an award-winning Hungarian mathematician and computer scientist from the University of Chicago.
 
26
But the proof was not peer-reviewed yet at the time of writing.
 
27
\(2^{c \log _2 n} = (2^{\log _2 n})^c = n^c\).
 
28
The empty language is the empty set of words, \(\emptyset \), so it does not contain any words at all. Admittedly, not a very useful language, but that makes it even more important to be able to check efficiently that one’s grammar does not describe this language.
 
29
This had already been observed by [16] who uses some of the results in [3].
 
Literatur
1.
Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. Proc. STOC’77. pp. 77–90, ACM (1977)
2.
Connolly, T., Begg, C.: Database Systems: A Practical Approach to Design, Implementation, and Management. 5th edition, Pearson (2009)
3.
Cook, S.A.: The complexity of theorem proving procedures. Proc. STOC ’71, pp. 151–158, ACM (1971)
4.
5.
Fraenkel, A.S., Lichtenstein, D.: Computing a perfect strategy for \(n*n\) chess requires time exponential in \(n\). J. Comb. Th. A 31, 199–214 (1981)MathSciNetCrossRefMATH
6.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)MATH
7.
8.
Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)
9.
Grohe, M., Schwentick, T., Segoufin, L.: When is the evaluation of conjunctive queries tractable? In Aharanov, D., Ambainis, A., Kempe, J., Vazirani, U. (eds): Proc. STOC’01, pp. 657–666, ACM (2001)
10.
Gualà, L., Leucci, S., Natale, E.: Bejeweled, Candy Crush and other match-three games are (NP-)hard. In: IEEE Conference on Computational Intelligence and Games, CIG, pp. 1–8, IEEE (2014)
11.
Hopcroft, J., Wong, J.: Linear time algorithm for isomorphism of planar graphs. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 172–184 (1974)
12.
Johnson, D.S.: A brief history of NP-completeness 1954–2012. In Götschel (ed.): Optimization Stories, Book Series, Vol. 6, pp. 359–376, Documenta Mathematica (2012)
13.
Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theor. Comput. Sci. 3(1), 105–117 (1976)
14.
15.
Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theor. Comput. Sci. 3(1), 105–117 (1976)
16.
Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Springer, New York (1972)CrossRef
17.
Levin, L.A.: Universal Sequential Search Problems\(^32\)(Russian original appeared in: Problemy Peredachi Informatsii 9 (3), 115–116). Problems of Information Transmission, 9:3, 265–266 (1973)
18.
Mai, H., Khurshid, A., Agarwal, R., Caesar, M., Godfrey, P., King, S.T.: Debugging the data plane with Anteater. ACM SIGCOMM Comput. Commun. Rev. 41(4), 290–301 (2011)CrossRef
19.
20.
Papadimitriou, C.H.: Lecture Notes in Computer Science. In: Degano, P., Gorrieri, R. (eds.) NP-completeness: A Retrospective. Marchetti-Spaccamela, A.: ICALP ’97, pp. 2–6. Springer, Heidelberg (1997)
21.
Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. Proc. PODS ’97, pp. 12–19, ACM (1997)
22.
23.
24.
25.
Vardi, M.: The complexity of relational query languages (Extended Abstract). In: STOC ’82, pp. 137–146, ACM (1982)
26.
Vardi, M.: On the complexity of bounded-variable queries (extended abstract). Proc. PODS ’95, pp. 266–276, ACM (1995)
27.
28.
29.
30.
Xie, G.G., Zhan, J., Maltz, D., Zhang, H., Greenberg, A., Hjalmtysson, G., Rexford, J.: On static reachability analysis of IP networks. In: Proceedings of the IEEE INFOCOM 2005, Vol. 3, pp. 2170–2183(2005)
31.
Yannakakis, M.: Algorithms for acyclic database schemes. In: Proceeding of the 7th Very Large Data Bases ’81 Vol. 7, pp. 82–94 VLDB Endowment IEEE (1981)
Metadaten
Titel
Complete Problems
verfasst von
Bernhard Reus
Copyright-Jahr
2016
Buch
Limits of Computation

Print ISBN: 978-3-319-27887-2

Electronic ISBN: 978-3-319-27889-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-27889-6_20