History


Help on query formulation
Introduction into $NP$-hard problems. (Einführung in $NP$-schwere Probleme.) (German)
Wurzel 45, No. 2, 26-31 (2011).
Aus der Einführung: Beim Optimieren sind zwei Aspekte von besonderer Wichtigkeit: Wie viel Zeit benötigt mein Algorithmus, um eine optimale Lösung zu finden, und wie viel Speicherplatz braucht er dafür, beispielsweise auf der Festplatte. Dieser Artikel beschäftigt sich mit der Laufzeit von Algorithmen und dem damit verbundenen P-NP-Problem. Dieses ist eine der interessantesten ungelösten Fragen der angewandten Mathematik: Gibt es für eine Vielzahl von mathematischen Problemen, für die bislang nur Algorithmen mit exponentieller Laufzeit bekannt sind, einen effizienteren, also polynomiellen, Lösungsalgorithmus?
From the introduction (translation): When doing optimizations, two aspects are especially important: How much time does my algorithm require to find an optimal solution, and how much memory space does it need for this, for example on the hard disk. The article deals with the running time of algorithms and the $P$-$NP$ problem involved. This is one of the most interesting unsolved issues of applied mathematics: Is there a more efficient, that is a polynomial, solution algorithm for a multitude of mathematical problems for which only algorithms with an exponential running time are known up to now?
Classification: P20 K30
Valid XHTML 1.0 Transitional Valid CSS!