nach oben

vorheriges Kapitel Common Problems Not Known to Be in P

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2016 | OriginalPaper | Buchkapitel

18. The One-Million-Dollar Question

Erstes Kapitel lesen

Autor: Bernhard Reus

Verlag: Springer International Publishing

Erschienen in: Limits of Computation

» Jetzt Zugang zum Volltext erhalten

Abstract

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

Jetzt einloggen Kostenlos registrieren

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Rubik’s cube is a three-dimensional combination puzzle invented by Ernő Rubik, a professor of interior architecture and design, to help explain three-dimensional geometry in 1974. The original cube consists of \( 3 \times 3 \times 3\) smaller cubes that rotate around 3 axes. It is considered one of the top-selling puzzle games of all time with allegedly more than 350 million cubes sold worldwide [ 6].

Currently, the fastest ever time to solve the Cube is 5.25 seconds recorded by Collin Burns, an American teenager, in April 2015. This is according to the “World Cube Association” [ 11], and one may be surprised to hear that such an organisation exists.

Recall that the exponent can be a polynomial in n.

The kind of nondeterminism that corresponds to requiring that all computation sequences need to be accepting is called “ demonic” instead.

With length 7.

We have used “dove-tailing” in Chap. 9, Exercise 1(d) to show that if a set and its complement are both semi-decidable then the set is already decidable. The “dove tail” is split and the deterministic computation we do needs to be split up into all those potential computations (in a lock step way in order to avoid running into a non-terminating computation).

With \(k\ge 3\).

If the number is represented in binary then use \(\mathrm {log}_{2} K\) instead of K.

Moj \(\dot{\text {z}}\)esz Presburger (27 December 1904–1943?) was a Polish mathematician, logician, and philosopher and a student of Alfred Tarski. In his memory the European Association for Theoretical Computer Science created the annual Presburger Award for young scientists in 2010.

Michael J. Fischer (born April 20, 1942) is an American (applied) mathematician and computer scientist and an ACM Fellow. He is known for his work in concurrency and he is a pioneer of electronic voting systems.

Michael Oser Rabin (born September 1, 1931) is an Israeli computer scientist. Together with Dana Scott he won the Turing Award for their work on finite nondeterministic automata in 1976.

Elementary? Not really, my dear Watson. The name “elementary” was chosen for that class of problems as they are still decidable and thus “elementary” in that sense (and only in that sense).

Note that one of them, the Poincaré Conjecture has been proved in 2002 by Russian mathematician Grigoriy Perelman who was eventually awarded the Millennium Prize from the Clay Institute in 2010 but declined the prize, as he declined many other prestigious awards before.

The most recent such proof attempt that received wide press coverage was submitted in August 2010 by Vinar Deolalikar from HP Labs.

In Chap. 20 Exercise 15 we will see a concrete problem that is not in NP.

Aaronson, S.: Guest column: NP-complete problems and physical reality. ACM Sigact News 36(1), 30–52 (2005) CrossRef

Aaronson, S.: Quantum Computing Since Democritus. Cambridge University Press, Cambridge (2013) CrossRefMATH

Cook, S.A.: Can computers routinely discover mathematical proofs? Proc. Am. Philos. Soc. 128(1), 40–43 (1984)

Clay Mathematics Institute: Millennium problems, available via DIALOG. http://www.claymath.org/millennium-problems. Cited on 16 June 2015

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

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

Fischer, M.J., Rabin, M.O.: Super-exponential complexity of Presburger arithmetic. Proc. SIAM-AMS Symp. Appl. Math. 7, 27–41 (1974) MathSciNetMATH

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)

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

Buch

Limits of Computation

Print ISBN: 978-3-319-27887-2

Electronic ISBN: 978-3-319-27889-6

https://doi.org/10.1007/978-3-319-27889-6

DOI

https://doi.org/10.1007/978-3-319-27889-6_18

Autor:

Bernhard Reus

Verlag

Springer International Publishing

Sequenznummer

Kapitelnummer

Chapter 18

Premium Partner

Bildnachweise