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:
Introduction Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

11. Hard Problems and (Limited) Sloppiness

verfasst von : Magnus Lie Hetland

Erschienen in: Python Algorithms

Verlag: Apress

Einloggen

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

search-config
loading …

Abstract

■■■

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 Matchings, Cuts, and Flows
Nächstes Kapitel Pedal to the Metal: Accelerating Python
Fußnoten
1
You can assume that getting down from Pollux is easy enough. Perhaps there’s a water slide? And that all of this was built before Pollux got so impregnable. Perhaps there was a rockslide?
 
2
“An economics professor and a student were strolling through the campus. ‘Look,’ the student cried, ‘there’s a $100 bill on the path!’ ‘No, you are mistaken,’ the wiser head replied. ‘That cannot be. If there were actually a $100 bill, someone would have picked it up.’” (From Compensation, by G. T. Milkovich and J. M. Newman.)
 
3
Vinay Deolalikar. P is not equal to NP. August 6, 2010.
 
5
Actually, Impagliazzo’s definition of Algorithmica also permits some slightly different scenarios.
 
6
Note the “seems to.” We don’t really know whether P = NP, so the definition might actually be equivalent.
 
7
Although I don’t make a big fuss about it here, the fact that such problems exist is actually pretty weird.
 
8
We need to stick with a polynomial number of nodes, of course.
 
9
Both for this section and the following two, you might want to try to show that the examples in the initial paragraphs are, in fact, NP-hard.
 
10
To make it easier to follow the arguments in these sections, I’ll generally progress (using reductions) from seemingly simple problems to more expressive ones. In reality, of course, they’re all just as expressive (and hard)—but some problems hide this better than others.
 
11
This paragraph is probably easier to understand if you already know a little bit about linear programming. If you didn’t quite catch all of it, don’t worry—it’s not really essential.
 
12
Unless we want to take relativity or the curvature of the earth into account ...
 
13
Any infinite distances would break it, unless it was completely without edges or consisted of only two nodes.
 
14
Note that we always divide the larger of the two (optimum and approximation) by the smaller.
 
15
For the minimization case, just reverse the logic, and consider the ratio B/A.
 
16
Notice the use of “proof by cases” here. It’s a really useful technique.
 
17
I’m guessing he’d think of something better, though.
 
18
You might want to verify for yourself that the number of odd-degree nodes in any graph is even.
 
19
If you were minimizing, the bounds would, of course, be swapped.
 
20
And if you want to get fancy, you could always research some of the many heuristic search methods originating in the field of artificial intelligence, such as genetic programming and tabu search. See the “If You’re Curious ...” section for more.
 
Metadaten
Titel
Hard Problems and (Limited) Sloppiness
verfasst von
Magnus Lie Hetland
Copyright-Jahr
2014
Verlag
Apress
Buch
Python Algorithms

Print ISBN: 978-1-4842-0056-8

Electronic ISBN: 978-1-4842-0055-1

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-1-4842-0055-1_11