Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2014 | OriginalPaper | Chapter

11. Hard Problems and (Limited) Sloppiness

Author : Magnus Lie Hetland

Published in: Python Algorithms

Publisher: Apress

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

■■■

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Matchings, Cuts, and Flows
next chapter Pedal to the Metal: Accelerating Python
Footnotes
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.
 
Metadata
Title
Hard Problems and (Limited) Sloppiness
Author
Magnus Lie Hetland
Copyright Year
2014
Publisher
Apress
Book
Python Algorithms

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

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

Copyright Year: 2014

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

Premium Partner

    Image Credits