Although it is difficult to find efficient solutions to decision problems like the Travelling Salesman or Linear Integer Programming presented earlier, it turns out to be relatively easy to check whether a certain candidate solution actually is a solution for the given problem. As this appears to be such a common pattern in optimisation problems, a complexity class will be defined accordingly. The problem arises whether this new class is equal to the “good” class of polynomially decidable problems. This turns out to be the most famous open problem in Theoretical Computer Science. But not only this, it appears to have significant impact on the world of computing and even physics.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Fischer, M.J., Rabin, M.O.: Super-exponential complexity of Presburger arithmetic. Proc. SIAM-AMS Symp. Appl. Math.
7, 27–41 (1974)
MathSciNetMATH
8.
Presburger, M.: Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt (English translation: Stansifer, R.: Presburger’s Article on Integer Arithmetic: Remarks and Translation (Technical Report). TR84-639. Ithaca/NY. Department of Computer Science, Cornell University)). Comptes Rendus du I congrès de Mathématiciens des Pays Slaves, 1929, pp. 92–101 (1930)
9.
Stockmeyer, L.J.: The Complexity of Decision Problems in Automata Theory and Logic, PhD Thesis. MIT, Cambridge (1974)
10.
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: Proceedings of the Conference on Record of 5th Annual ACM Symposium on Theory of Computing, pp. 1–9. ACM (1973)
Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.
Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis. Jetzt gratis downloaden!
