{"entities":{"Q5925718":{"pageid":8102520,"ns":120,"title":"Item:Q5925718","lastrevid":39849710,"modified":"2025-01-27T18:54:49Z","type":"item","id":"Q5925718","labels":{"en":{"language":"en","value":"The complexity theory companion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1566499"}},"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":"Q5925718$B9606E02-7E6E-4021-B0F2-A356C159EEEB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6b08aa35e4edea5c6bad0bb627766f879dc8d012","datavalue":{"value":{"text":"The complexity theory companion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5925718$0A540459-DA39-448F-8B11-97CC5799BCAC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5dd52f01ae279bb7ffe4009f250905df5af1646a","datavalue":{"value":"0993.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5925718$6373E935-0897-4FEF-BAED-920A6088AF51","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"95d207a16ce6533a2e03f4685944467ead41f45c","datavalue":{"value":{"entity-type":"item","numeric-id":161382,"id":"Q161382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5925718$0B5838FA-204C-48B3-992A-A02F5FF39092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e4755808b3d16445db7144cb71da22e888d23a9","datavalue":{"value":{"entity-type":"item","numeric-id":161383,"id":"Q161383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5925718$114AEAC6-6BC5-400F-B739-95357003D994","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0f0a2acff5007574f811cbeec1fb72101c4611a9","datavalue":{"value":{"entity-type":"item","numeric-id":161384,"id":"Q161384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5925718$ED989D52-721F-41C0-B27C-23BDFB520943","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7ef592fcbe568fe20d1e22f6164adf86fbb75290","datavalue":{"value":{"time":"+2001-02-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5925718$533CE757-7A14-428A-BA75-75D701F474AD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5925718$F699E225-4E87-47CA-A41C-1FB8DF4634BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"98c5206e338942c77451c20a9a5ffe8ae1a4cf18","datavalue":{"value":"68-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5925718$ED8C4519-D2F0-40FA-A716-764D224F2B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5925718$C9239875-5B14-4AE5-B914-857EC6FB4141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5925718$8AAE0824-57EF-47D8-8BF6-ED917BF2A451","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0b3d5a69db4f9723ccd4bf4b1e27a1e0e44eb48","datavalue":{"value":"1566499","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5925718$BFAB1340-5A5F-4008-940E-EF044F710787","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5925718$A61120AD-25D6-4E14-83D4-2DC9E7510A39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5925718$F9759DE5-DE13-4F65-9CD5-9F5743F38DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bc1cc50e8d4b517f651118878724606a4faacd","datavalue":{"value":"reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q5925718$61FE169F-2A9F-402C-8B97-4F4B856E3DE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ff71c746b71b34e36571430b803101bb626c7fa","datavalue":{"value":"The book is intended for readers who seek an accessible, algorithmically oriented research-centered, up-to-date guide to several interesting techniques of computational complexity. In contrast to the organization of other books, each chapter of this book focuses on one particular technique in complexity theory. The technique is explained and the results achieved by it and its applications are presented. Each chapter is provided with bibliographic notes and a part containing open issues.    The book is divided into the following chapters: 1. The self-reducibility technique; 2. The one-way function technique; 3. The tournament divide and conquer technique; 4. The isolation technique; 5. The witness reduction technique; 6. The polynomial interpolation technique; 7. The nonsolvable group technique; 8. The random restriction technique; 9. The polynomial technique.    The book contains two appendices, the first presenting a concise overview on complexity classes, the second one on reductions.    The book present a survey on a great variety of recent interesting techniques in complexity. It falls well into the long line of surveys or surveys-like monographs emphasizing the special field of computational complexity starting with Wagner's and Wechsung's monograph of the same name (Zbl 0584.68062).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5925718$7893D525-7DB4-4940-B9E1-81F2AAE60507","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"02bc07e7fdf69b7795d4694a59f3d739066e6204","datavalue":{"value":{"entity-type":"item","numeric-id":259038,"id":"Q259038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5925718$FA1E8554-B0F6-4BC9-9860-F19006A35898","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":"Q5925718$2AB9610F-A272-460B-9BF7-CFA235708A4C","rank":"normal"}],"P1643":[{"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":"ce1a170d695cd30e410d20844590b57e05e1fb3a","datavalue":{"value":{"amount":"+0.86536527","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$15F8CE76-6F37-432A-B9E7-9713D4B8BBAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"766438340f32cb13d9476b90703ce8a515e4febf","datavalue":{"value":{"entity-type":"item","numeric-id":4554784,"id":"Q4554784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbb797ecd7ee08e5893469029625932e68526014","datavalue":{"value":{"amount":"+0.8617101","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$AAA23494-1217-4825-BA7F-F311D9268FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a1a3df041a518d453788025e109a06480366569","datavalue":{"value":{"entity-type":"item","numeric-id":5900112,"id":"Q5900112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2d5fc5f98a3688ae5b68086a2db653776ebc63f","datavalue":{"value":{"amount":"+0.8612532","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$8A74B248-8AB6-4D23-96F0-C2BBF7F1FC38","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":"27d4bc41989936383629a0807d65752776fd099a","datavalue":{"value":{"amount":"+0.8576193","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$B8668FFC-FDB6-4C04-9315-075994EB0DDB","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":"d38eb4a81b01e7d69c8beaa86aaa56bed36b540b","datavalue":{"value":{"amount":"+0.8483125","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$FF98EBB8-D1C2-4913-B6E2-E4CAF046C985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38e1eabb7fc35b211ca98c9292b60a55b2bdaf94","datavalue":{"value":{"entity-type":"item","numeric-id":465686,"id":"Q465686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c51f89f0d2c8612bf00778b3f8ac9aa00f86fdc","datavalue":{"value":{"amount":"+0.84699786","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$F9F60852-C15C-46DF-B3B7-5B973556075A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a29d770ed386cf5da2637beeaa4b875135bcffd0","datavalue":{"value":{"entity-type":"item","numeric-id":4692882,"id":"Q4692882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5507f4638c20ca53f0202ced93096f08119082f1","datavalue":{"value":{"amount":"+0.84376055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$B3C0A2B5-B760-4AD1-BDAC-2A0114ABE6F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c748c7a4e0b37d1258408938ebbc7cd9a4f1c70","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8827e6731bb48a9c816fa94e618f9c679e825f0","datavalue":{"value":{"amount":"+0.8408342","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$B98FF14D-9187-493C-BF4C-F5EB912F0DEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cb61acf9921076796dfea294d4bc92ab41f7210","datavalue":{"value":{"entity-type":"item","numeric-id":3707408,"id":"Q3707408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3af93e5c306cb8c8b3526c8cac1ae105dde42c4c","datavalue":{"value":{"amount":"+0.8397167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5925718$A283929F-02C1-4C51-B8C4-1AFD74A0107D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5925718","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5925718"}}}}}