14  ``Harte'' Probleme

Literatur: Verschiedenes aus [CLR90] oder "ahnlichem. Vor allem Kapitel 36. Dazu Kapitel 11 aus [HU79]. Ein (schwieriges) Standardwerk zur Komplexit"atstheorie ist [Pap94].

Inhalt Komplexit"atsklassen P und NP ·Algorithmisch harte Probleme

• Bisher nur: leichte Probleme³⁷: Laufzeit O(n^k) (polynomiell, oft quadratisch)
• allgemeine Techniken f"ur leichte Probleme
  • Greedy: entscheide dich immer f"ur den augenblicklich gr"o"sten Gewinn
  • Divide-and-Conquer: zerlege das Problem in unabh"angige Teilprobleme und l"ose diese rekursiv
  • Relaxation
  • dynamische Programmierung als ``Verallgemeinerung'' von divide-an-conquer
  • viele andere:
    • branch-and-bound
• inh"arent harte Probleme
  • einfache Strategien scheitern; schlimmer: effiziente, komplexere Strategien ebenfalls nicht bekannt
  • oft Optimierungsprobleme
  • oft praktisch relevant: Plazierungen, Scheduling, Kostenminimierung, Probleme aus der Logik, Netzwerkdesign, Zahlentheorie, ...

• TSP: ber"uhmtes NP-vollst"andiges Problem
• gegeben:
  • ungerichteter Graph (Knoten = ``St"adte'')
  • d: E ® R<sup>+</sup> (``Distanz'')
• Gesucht: Teilgraph G' = (V',E') als Kreis mit V' = V und minimalen Kosten (``beste Rundreise'')³⁸, d.h.

  min p

  n å i=1

  d(p(i),p(i+1))

  wobei n+1 sei 1 und das Minimum werde "uber alle Permutationen p gebildet.

• Formales Modell: Turingmaschinen o. "a.
• Klassifizierung von Problemen nach ihrer Komplexit"at (meist Laufzeit)
• Unterscheidung
  • deterministisch (DTIME) oder
  • nicht-deterministische (NTIME) Komplexit"at
• Beispiel: DTIME(n): linear

• Alternativ: NP enth"alt die Probleme, die polynomiell verifiziert werden k"onnen
• P = ÈDTIME(nⁱ)
• NP = ÈNTIME(nⁱ)
• "ahnliche Klasse auch f"ur Speicherkomplexit"at (DSPACE, NSPACE)

• ber"uhmte Klasse schwerer Probleme
• Klasse = ``gleichschwere'' Probleme
• Status unbekannt, wichtiges offenes Problem
  • gibt es eine polynomielle L"osung f"ur derartige Probleme oder
  • gibt es eine nicht-polynomielle untere Absch"atzung

• NP = P oder NP ¹ P

• Reduktion: Vergleich der ``Schwere'' von Algorithmen
• analog der Klassenbildung der Berechenbarkeitstheorie
  • Beispiel: Klasse der rekursiv-aufz"ahlbaren Probleme (r.e.)
  • Reduktion als Hilfsmittel zu Aussagen "uber Entscheidbarkeit/Rekursive Aufz"ahlbarkeit etc.
  • Reduktion: Algorithmus der eine Instanz eines Problems A in eine Instanz eines Problems B "ubersetzt.
  • Þ falls B entscheidbar, re. etc., dann A entscheidbar, oder umgekehrt, falls A unentscheidbar, dann B ebenfalls.
  • Halteproblem: falls eine
• Komplexit"atstheorie: nicht mehr nur Ja/Nein: Komplexit"at der "Ubersetzung mu"s ber"ucksichtigt werden.

• Reduktion: zweiseitig anwendbar
  1. Zum Beweis der Existenz eines effizienten Algorithmus
  2. Beweis der Nicht-Existenz eines effizienten Algorithmus
• Þ Begriff der Vollst"andigkeit

• Þ Definition von NP-vollst"andigen Probleme: die ``maximalen'' in NP.

• Beispiel: Hamiltonsche Kreise £_p TSP
  • ber"uhmtes Graphentheoretisches Problem
  • "ahnlich TSP, aber kein Optimierungsproblem
  • gegeben: ungerichteter Graph
  • gesucht: gibt es einen einfachen Pfad der alle Knoten enth"alt
• Reduktion auf das TSP-Problem: bilde den vollst"andigen Graphen aus den gegebenen Knoten, gewichte die Kanten mit 1 f"ur alle Kanten bereits in G, die anderen gewichte mit 2.
• die umgekehrte Reduktion ist viel schwerer.

• berechtigte Frage: gibt es NP-vollst"andige Probleme?
  • Erf"ullbarkeit von Boolescher Logik/Schaltkreisen
  • Problem des Handlungsreisenden
  • Hamiltonsche Graphen, Max-Clique, ......
  • z.B. Graphenprobleme: MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM EDGE DOMINATING SET, MINIMUM INDEPENDENT DOMINATING SET, MINIMUM GRAPH COLORING, MAXIMUM ACHROMATIC NUMBER, MINIMUM EDGE COLORING, MINIMUM FEEDBACK VERTEX SET, MINIMUM FEEDBACK ARC SET, MINIMUM MAXIMAL MATCHING, MAXIMUM TRIANGLE PACKING MAXIMUM H-MATCHING, MINIMUM BOTTLENECK PATH MATCHING, MINIMUM CLIQUE PARTITION, MINIMUM K-CAPACITATED TREE PARTITION, MAXIMUM BALANCED CONNECTED PARTITION, MINIMUM CLIQUE COVER, MINIMUM COMPLETE BIPARTITE SUBGRAPH COVER, MINIMUM VERTEX DISJOINT CYCLE COVER, MINIMUM EDGE DISJOINT CYCLE COVER, MINIMUM CUT COVER, ...