nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

19. How Hard Is a Problem?

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

KI-gestützte Suche

Aus

Abstract

Since no concrete lower bounds for problems in NP are known, we identify the “hardest” problems in this class. To express the “harder” (or rather “not simpler than”) relationship one uses the concept of reduction. In order to ensure that one does not get out of the class of polynomial time verification, the reduction function is required to be computable in polynomial time. One can then show that if P \(\ne \) NP is assumed, none of those “hardest” problem in NP can actually have a polynomial time solution. In other words, to show that P = NP it suffices to find a polynomial time solution for any of the “hardest” problems in NP.

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 The One-Million-Dollar Question

Nächstes Kapitel Complete Problems

Richard Manning Karp (born January 3, 1935) is an American computer scientist, most known for his work in complexity and computability theory for which he received, among many other awards, the Turing Award in 1985.

There are other variations of reduction where e.g. the question “is in B?” can be asked several times.

Emil L. Post (February 11, 1897–April 21, 1954) was an American mathematician and logician, also famous for his “Post System” that can be used as a model of computation.

This follows from the definition of time measures as the construction of large expressions is accounted for in the time measure. For each time unit consumed one can at most produce one “bit” of the output.

“Another last minute terminology substitution happened when Aho, Hopcroft, and Ullman substituted “NP-complete” for “Polynomially-complete” in their text on Algorithms even though they had already gotten galley proofs using the original name. The name was changed at that late date as the result of a poll conducted throughout the Theoretical Computer Science community (suggested names were NP-Hard, Herculean Problem, and Augean Problem)” (see footnote 6) [6]. It was actually Knuth himself who triggered the discussion about the terminology in [5].

In Greek mythology Heracles (Hercules) was known for his strength. As a penance for having killed his family, he had to perform ten labours, the fifth of which was to clean the stables of Augeas in one day. It should be noted that Augeas was known for having the most cattle in the country. Heracles solved this task by rerouting the local rivers into the stables (which was then considered cheating, but this is another story...).

For those who know about the properties of order relations: relation \(\le _P\) is not totally ordered, it is not even quite an order. It is just a so-called preorder (or quasi-order). It is reflexive and transitive but not anti-symmetric, i.e. it does not hold that \(A\le B\) and \(B\le A\) implies \(A=B\). We can have, for instance two different “hardest” problems such that each must be reducible to the other but they are different problems still.

See Proposition 2.1.

Baker, T.P., Gill, J., Solovay, R.: Relativizations of the P =? NP question. SIAM J. Comput. 4(4), 431–442 (1975)MathSciNetCrossRefMATH

Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)MATH

Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theor. Comput. Sci. 3(1), 105–117 (1976)MathSciNetCrossRefMATH

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

Knuth, D.E.: Terminological proposal. SIGACT News 6(1), 12–18 (1974)MathSciNetCrossRef

Knuth, D., Larrabee, T., Roberts, P.M.: Mathematical Writing No. 14. Cambridge University Press, Cambridge (1989)MATH

Ladner, R.: On the structure of polynomial time reducibility. J. ACM (JACM) 22(1), 155–171 (1975)MathSciNetCrossRefMATH

Titel: How Hard Is a Problem?
verfasst von: Bernhard Reus
Verlag: Springer International Publishing
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_19

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"