scientific article; zbMATH DE number 1313596

MaRDI QIDQ4256192zbMATH OpenFDO

Authors Christoph Karg

Publication date 5 July 1999

zbMATH Keywords

problem complexitytest instances

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25)

Review text

Diese Arbeit hat die Average-Case Komplexität von Berechnungsproblemen zum Thema. Sie ist folgendermaßen gegliedert: Im ersten Kapitel werden die benötigten Notationen und Begriffe aus der Komplexitätstheorie und Mathematik eingeführt. Innerhalb des zweiten Kapitels beschäftigen wir uns damit, wie man die Average-Case Komplexität eines Algorithmus messen kann. Im dritten Kapitel untersuchen wir structurelle Aspekte der Durchschnittskomplexität. Wir unterscheiden hierbei zwischen deterministischen und nichtdeterministischen Berechnungen und beschränken uns auf die Ressourcen Rechenzeit und Speicherplatz. Das vierte Kapitel befaßt sich mit der Durchschnittskomplexität von NP-vollständigen Problemen. Im fünften und letzten Kapitel dieser Arbeit steht die Generierung von Testinstanzen im Mittelpunkt. Unser Ziel ist es, die globale Korrektheit von Algorithmen für NP-Suchprobleme mit bezüglich einer vorgegebenen Wahrscheinlichkeitsverteilung zufällig erzeugten Eingaben zu testen.

Recommendations

• scientific article; zbMATH DE number 1332677
• The complexity of generating test instances
• On the complexity of test case generation for NP-hard problems
• Average case complexity, revisited

Cited in

(3)

• scientific article; zbMATH DE number 1332677 (Why is no real title available?)
• The complexity of generating test instances
• On the complexity of test case generation for NP-hard problems

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4256192)