2016 | OriginalPaper | Buchkapitel
Tipp
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Erschienen in:
Limits of Computation
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
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Anzeige
1.
Aaronson, S.: Guest column: NP-complete problems and physical reality. ACM Sigact News
36(1), 30–52 (2005)
CrossRef
2.
3.
Cook, S.A.: Can computers routinely discover mathematical proofs? Proc. Am. Philos. Soc.
128(1), 40–43 (1984)
4.
Clay Mathematics Institute: Millennium problems, available via DIALOG.
http://www.claymath.org/millennium-problems. Cited on 16 June 2015
5.
Clay Mathematics Institute: P versus NP problem, available via DIALOG.
http://www.claymath.org/millennium-problems/p-vs-np-problem. Cited on 16 June 2015
6.
Cube Facts: Rubik’s
\(^{\textregistered }\)—the home of Rubik’s cube, available via DIALOG.
https://uk.rubiks.com/about/cube-facts/. Cited on 30 June 2015
7.
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)
11.
World Cube Association: Results, available via DIALOG.
https://www.worldcubeassociation.org/results/regions.php. Cited on 30 June 2015
- Titel
- The One-Million-Dollar Question
- DOI
- https://doi.org/10.1007/978-3-319-27889-6_18
- Autor:
-
Bernhard Reus
- Sequenznummer
- 18
- Kapitelnummer
- Chapter 18