{"entities":{"Q4520107":{"pageid":6549700,"ns":120,"title":"Item:Q4520107","lastrevid":108668465,"modified":"2026-11-09T17:47:28Z","type":"item","id":"Q4520107","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1542049"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4520107$2B62F75C-78C8-496C-AC23-011EBD909614","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c501ddb223dc029b4c18498a8d036574f8d3c10","datavalue":{"value":"0965.68024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4520107$F5715B94-B115-48B7-BBFB-94649BBC0A65","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d19271338ab1f986510acb204ee362887c758de3","datavalue":{"value":{"entity-type":"item","numeric-id":751269,"id":"Q751269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4520107$CB156A68-DC0A-47EC-8491-2AD60962EE36","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5292801f0dd79298539819e0a4ac0e822803e06","datavalue":{"value":{"time":"+2000-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4520107$F9CDD2D7-9EC0-4386-8A04-D1E385B574B2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4520107$AEA326AC-BC8B-406B-94BB-31DDD60AAFC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"98c5206e338942c77451c20a9a5ffe8ae1a4cf18","datavalue":{"value":"68-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4520107$6B353B77-8792-4E1F-BF77-D9AF922D41A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4520107$B6E97792-BC0A-4AAF-956B-0A0F7906F39A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4520107$C02BBD02-72EE-4C7F-A38D-71F4838CE9DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4520107$3C5ED04D-3025-4FC1-BED8-54ADC6B5F88E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b15c6f9e95d8027e2294866f3922e8b3368b5f43","datavalue":{"value":"1542049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4520107$423E845D-CD6E-42B9-9D9B-7D085657A338","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$AA6F3B9E-401B-4213-A55E-F89F74285507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$69D7B402-5C89-4A0C-9C26-8C116054F184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4568ddf22cb40e2390723c95f04c4d2c600c129","datavalue":{"value":"determinism versus nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$FF3652E7-2D43-4DE5-9E83-A27CFE9C0337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8b792d7c10660a0a5a9e4608900e8b28b6a6208","datavalue":{"value":"time versus space","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$555BF5C1-60B7-49B2-8407-9D340B52B74C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bc1cc50e8d4b517f651118878724606a4faacd","datavalue":{"value":"reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$1308265F-0A6E-4980-A092-F18F76B9BA25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6816fdf79dd11ac09d9af4886c02baab03d2cf9","datavalue":{"value":"completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$A2F813EB-D29F-47BA-8791-1C4557FD4A74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43d9ae3dc1ef668dad046fdfde4adcb2eacf8fa8","datavalue":{"value":"probabilistic complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$1AC18ACD-8737-40FC-8156-ACCF697966A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$B02152B8-A245-44BB-AE5C-96F5F843219C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1e10e42df7624f4c44e25a596575282d4d3f781","datavalue":{"value":"Boolean hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$B87962E4-5C52-4929-A4B1-240D093170A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3fb06cdd1f6b7cb08083bda4915b8b774c186edb","datavalue":{"value":"leaf languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$F05831A3-214E-47AB-ADA7-2DA530F47307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d435b6f8fa5aefb69319ed8da57a094f7d5a961","datavalue":{"value":"counting classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$072FD628-5095-4D97-9A8E-FCC3B358DB07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e33be85e6144011469b924461155c4e621980d55","datavalue":{"value":"complexity classes of functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$79B392CF-ADF7-46CA-8BBE-CEBF80E35D10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"008c70e766fc4d68d17a2a73ce059b3504dee5b7","datavalue":{"value":"lowness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$83AAA767-F7E6-40E6-9FCC-67DC1C3CF77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e23327e0505c1f7dc40922ee44ccebbc98309229","datavalue":{"value":"highness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$ABC5A339-01DF-4BCD-8C87-A0CF2F0C2670","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4520107$E900682B-E651-442A-BF20-62DEB370D914","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"052c7234a28ea27652eef501a48ae1cb345fe9f7","datavalue":{"value":{"entity-type":"item","numeric-id":4039803,"id":"Q4039803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c67a9305ffa3b6d1ffe482b9859d8fc3121d259","datavalue":{"value":{"amount":"+0.8146746158599854","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4520107$4E3336A7-D9CA-4EFE-8992-6091997947D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39c38a0ee02222b659cac5074b4c21f66d0870af","datavalue":{"value":{"entity-type":"item","numeric-id":2492014,"id":"Q2492014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef90b6b6df0b10185aa1f7e861b22c7fb210d320","datavalue":{"value":{"amount":"+0.813460111618042","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4520107$5168C7C4-6DC8-4C88-BAC9-D4D8E8AB84F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fd2ccebec9fe69cb83cb101f499a8a66ad47655","datavalue":{"value":{"entity-type":"item","numeric-id":3993545,"id":"Q3993545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cadbcfbb250ed9d354af64d8a396cdb1ec3a93ad","datavalue":{"value":{"amount":"+0.8129368424415588","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4520107$2695A725-40FF-426E-879D-B0501D31C5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc31ca9ba180f13b94e0e8549bee521365bdf28d","datavalue":{"value":{"entity-type":"item","numeric-id":5320667,"id":"Q5320667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceaa015b1d92a277a80f01c6422146fd1c9c370a","datavalue":{"value":{"amount":"+0.809912383556366","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4520107$00E76244-F530-4C20-B711-0767D2D91C8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"320bc85ed1ebca8cba54b9109fe66a082dd8bd5f","datavalue":{"value":{"entity-type":"item","numeric-id":4942157,"id":"Q4942157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4be5e2c3c18cb013222811d2b438bde0d504956","datavalue":{"value":{"amount":"+0.8088446855545044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4520107$82C12200-7FF7-46C2-832E-90C4D58419B7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"852d743ee301a2afdcf75923243df8a7125b3fe6","datavalue":{"value":"Der Autor charakterisiert das Buch im Vorwort als ``eine Einf\u00fchrung in die Komplexit\u00e4tstheorie, die auch f\u00fcr Nichttheoretiker noch lesbar ist. Es f\u00fchrt gleichzeitig auf ausgew\u00e4hlten Gebieten an den aktuellen Forschungsstand heran.'' Genauer geht es um Berechnungskomplexit\u00e4t auf der Grundlage des Berechnungsmodells der Turingmaschine, und es werden haupts\u00e4chlich die Komplexit\u00e4tsmasse Zeit und Raum betrachtet. In den ersten vier Kapiteln (mit etwa 100 Textseiten) wird in z\u00fcgiger, an den grundlegenden Ideen und Zusammenh\u00e4ngen orientierter Darstellungsweise im wesentlichen das Fundament der klassischen Komplexit\u00e4tstheorie entwikkelt: 1. Zeit- und Raumkomplexit\u00e4tsklassen, Blumsche Axiome, Hierarchie- und L\u00fcckens\u00e4tze, Bandkompression und Beschleunigung, Beweisbeispiele f\u00fcr untere Schranken; 2. die Komplexit\u00e4tsklassen L, NL, P, NP und PSPACE, Reduzierbarkeiten zwischen Sprachen und vollst\u00e4ndige Probleme in NL, P und NP; 3. polynomialzeitbeschr\u00e4nkte tt- und T-Reduzierbarkeit, Polynomialzeithierarchie, alternierende Turingmaschinen und Komplexit\u00e4tsklassen, Relativierungen des P-NP-Problems, das Konzept der Blattsprachen; 4. S\u00e4tze von Savitch bzw. Immerman/Szelepcsenyi, blockrespektierende Turingmaschinen und ein Pebble-Spiel auf Graphen f\u00fchren zur raumeffizienten Simulation zeitbeschr\u00e4nkter Maschinen, DLINTIME \\(\\subset\\) NLINTIME, D \\(\\not=\\) ND f\u00fcr linear zeitbeschr\u00e4nkte Turingmaschinen. Kapitel 5 erg\u00e4nzt dieses Fundament durch die Problematik der d\u00fcnnen vollst\u00e4ndigen bzw. harten Sprachen f\u00fcr NP und verwandte Klassen bez\u00fcglich verschiedener Reduzierbarkeiten. Es ergeben sich Zusammenh\u00e4nge zu nichtuniformen Komplexit\u00e4tsklassen wie auch zum Isomorphieproblem, ob alle NP-vollst\u00e4ndigen Mengen untereinander polynomial isomorph sind. Der zweite Teil des Buches behandelt dann ausgew\u00e4hlte Themenkomplexe, zu deren Entwicklung und Untersuchung der Autor meist selbst wesentlich beigetragen hat. Wir versuchen, die Inhalte stichpunktartig zu umrei\u00dfen: Kapitel 6 besch\u00e4ftigt sich ausf\u00fchrlich mit der Hausdorffschen Hierarchie \u00fcber NP, auch als Boolesche Hierarchie bekannt. Ihre Klassen werden durch geeignete Akzeptierungstypen und spezielle tt-Reduzierungen auf NP charakterisiert sowie vollst\u00e4ndige Probleme angegeben. Enge Beziehungen zur Fragehierarchie, Betrachtungen zum Kollabieren der Hierarchie und zur Reihenfolge von Orakelabfragen erg\u00e4nzen das Bild. Die im Kapitel 7 betrachteten Z\u00e4hlklassen werden durch Forderungen an die Anzahl akzeptierender Pfade definiert. Diese Verallgemeinerungen des Akzeptierungsverhaltens bei NP und coNP liefert spezielle Blattsprachen. Ein typisches Beispiel ist die Parit\u00e4tsklasse \\(\\oplus\\)P. Zus\u00e4tzlich geforderte Eigenschaften der akzeptierenden Maschinen liefern die sogenannten promise-Klassen, wie beispielsweise Valiants UP. Die probabilistischen Komplexit\u00e4tsklassen, deren Studium das 8. Kapitel gewidmet ist, k\u00f6nnen ebenfalls h\u00e4ufig als Z\u00e4hlklassen aufgefasst werden. Die Darstellung als Blattsprachen, die mit Hilfe von Quantoren unter Einbeziehung des Mehrheitsquantors definiert werden, f\u00fchrt auch auf die Arthur-Merlin-Klassen. Das Studium entsprechend definierter Operatoren auf Komplexit\u00e4tsklassen m\u00fcndet in Ergebnissen von Toda \u00fcber Beziehungen zwischen probabilistischen Klassen und der Polynomialzeithierarchie. Komplexit\u00e4tstheoretische Untersuchungen zur Berechnung von Relationen bzw. Funktionen durch deterministische oder nichtdeterministische Maschinen stellen eine naheliegende Verallgemeinerung der vorwiegend auf Entscheidungen und Erkennungen ausgerichteten herk\u00f6mmlichen Komplexit\u00e4tstheorie dar. Kapitel 9 gibt die hierzu bekannten Resultate wider. So liefert die Anzahlbestimmung von L\u00f6sungen von Berechnungsproblemen, die zu Entscheidungsproblemen geh\u00f6ren, die Klasse \\(\\sharp P\\). Der Wunsch, L\u00f6sungen zu konstruieren, f\u00fchrt auf Betrachtungen zur Selbstreduzierbarkeit von Mengen und zur Suche nach optimalen L\u00f6sungen. Wieder ergeben sich enge Zusammenh\u00e4nge zur klassischen Theorie. Das abschlie\u00dfende Kapitel 10 ist den low- und high-Hierarchien gewidmet und diskutiert das Problem der Graphisomorphie. Zusammenfassend ist festzustellen, dass das vorliegende Buch seine Zielstellung, eine n\u00fctzliche Erg\u00e4nzung der vorhandenen Lehrb\u00fccher und Monographien zur Komplexit\u00e4tstheorie zu sein, voll erreicht. Die sehr kompakte Darstellung der grundlegenden Resultate in den ersten f\u00fcnf Kapiteln ist als Richtschnur und begleitende Lekt\u00fcre f\u00fcr entsprechende Vorlesungen sehr zu empfehlen. Die in den Kapiteln 6 bis 9 behandelten Themenkomplexe sind hier erstmals in monographisch zusammenfassender Weise pr\u00e4sentiert, wodurch sich dieser Teil als Grundlage und Handbuch f\u00fcr speziellere Lehrveranstaltungen und Forschungsseminare empfiehlt.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4520107$62097FE5-BC27-4BBF-B6C0-ED4B9FBBE396","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4520107","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4520107"}}}}}