{"entities":{"Q640476":{"pageid":642324,"ns":120,"title":"Item:Q640476","lastrevid":63216120,"modified":"2026-04-11T11:23:50Z","type":"item","id":"Q640476","labels":{"en":{"language":"en","value":"Computability and complexity theory."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5960137"}},"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":"Q640476$200CEC60-FBB4-4946-AD0E-FFC1E49C1615","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3ac2ce2e0763cfb3a4a80e0902a236b1504fb600","datavalue":{"value":{"text":"Computability and complexity theory.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q640476$2D752FD7-CBAD-4952-A007-827662913D3B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f706864e50fb3d45ccba9a73d1dbec54b04dae5","datavalue":{"value":"1248.68192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$236D32A5-45F2-4138-9BFA-B9B178945375","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d670144bd90b485b8f85122cfc3391b0bfc52f6f","datavalue":{"value":"10.1007/978-1-4614-0682-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$95CEE685-F7DE-432E-B171-E830103B3ABC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea55fa9123ea51f6ee4c733595d5dafa5f40d823","datavalue":{"value":{"entity-type":"item","numeric-id":161377,"id":"Q161377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640476$DF3053E1-3D34-49C3-897B-5DDA7762D748","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9767fe8dd1d6f9791ae763e9a67550b5f9aa27e1","datavalue":{"value":{"time":"+2011-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q640476$D67E6DA8-EB78-488B-AC65-392189E2CA44","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e92b73d0e479dd90c13a493b94975012b2a855b8","datavalue":{"value":"This book is intended to serve as a textbook for an introductory graduate course in theoretical computer science. According to the conviction of the authors that the important topics to teach at this level are the fundamental models of computation, the limits of computation, and the distinction between feasible and intractible, the different chapters of the book cover Turing machines and Church's thesis, undecidability, complexity measures and relations among them, nondeterminism and NP-completeness, relative computability, nonuniform complexity, parallelism and uniform circuit families, probabilistic classes, counting classes, and interactive proof systems. With this diverse spectrum of topics the book is even suitable as a text for a two semester graduate course. Though the topics are treated in depth and not only surveyed, they address all graduate students, not only those that will specialize in complexity. The book provides a solid background for the latter group that will have to consult further textbooks for more specialized topics on, e.g., circuit complexity, descriptive complexity, the PCP theorem, etc.","type":"string"},"datatype":"string"},"type":"statement","id":"Q640476$D123B685-FA15-48F0-8FD9-7ACDF502399E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cda603722202722f19339c0e84295bbe19098fb","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640476$8F04796F-481F-43A1-9D21-B737923B9CDD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23e7cdaf2e82f5cc864274e843d1c5be36653b9f","datavalue":{"value":"68Q01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$A3D32270-BA93-4B40-AB34-75788C4D10C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$3FB0A4DB-181B-4A38-801F-D7375730BAAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$1177ACA8-0AA3-43A4-8571-440CC2B1FA84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$4A825F84-2972-411B-9657-81D7044A0AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$6BECDCAF-5D3B-4B6E-9727-B7C60A13C1F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$74FAD156-F851-4B58-824C-F14D7F770436","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6206a1b063b1cc69402ccb1a717110266f962984","datavalue":{"value":"5960137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$CD162DC2-0878-4F13-8AA2-988D3945AFD9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f2891ec95ee556b0ac2cc2dddee3d77811bd94","datavalue":{"value":"computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q640476$D9F6DD1E-4B84-467C-9F17-A37B32625B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q640476$126D1186-E138-4C31-8337-46E950B22116","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q640476$5032DBBD-98CB-4972-8651-4813B745AC7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q640476$68C15911-3C08-4F52-A4D5-5600BC932384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"496fb62b5fbbae0889439900bccaa24ccd7b815b","datavalue":{"value":"randomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q640476$8597C2C6-7387-4331-893B-8059336C3F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5540e3a97aefc78b1cc58b39eaa31222058ad3d","datavalue":{"value":"counting complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q640476$534F836E-C2C9-48C3-82C7-D20CA1BF6267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a71b0fd9ded21190d6a828cc2fff4bf80dc80df6","datavalue":{"value":"interactive proof","type":"string"},"datatype":"string"},"type":"statement","id":"Q640476$BA80C494-58A9-411E-8E47-BD447599A31F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"24978249bb6f26d3c70c78605ce95b13704fc350","datavalue":{"value":{"entity-type":"item","numeric-id":161379,"id":"Q161379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640476$C71AF2CF-E29F-4438-9513-34F47F1AC6FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29b02350197f27ae1879c4b07e2f60550fcfbf54","datavalue":{"value":{"entity-type":"item","numeric-id":161380,"id":"Q161380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640476$A6E56F10-0B82-4E89-86C4-15033BD5C451","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":"Q640476$AAC9C6CB-5D01-4D9E-B57E-43AB50650C51","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd053e4dd5e25bfcc14dc4bc9b08ff9ec0d184ea","datavalue":{"value":"https://doi.org/10.1007/978-1-4614-0682-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q640476$4355A1BB-7EDC-47DE-A6F3-648DE90A55BF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"17a8ccdd41fa546439ffa6dd0228597b68217107","datavalue":{"value":"W4298156820","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640476$3A7F1F11-FA79-49BA-B61B-685C92810D49","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b06c192f57742c792e3942dc82392a7ef993e13","datavalue":{"value":{"entity-type":"item","numeric-id":5925717,"id":"Q5925717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02bb5a92d5a80992b3f62a587875c1d898472106","datavalue":{"value":{"amount":"+0.93007797","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":"Q640476$D078E56F-655C-4169-98B0-77943158BA6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48489563ac10f4036f1f210094c40c5647f3aaaf","datavalue":{"value":{"entity-type":"item","numeric-id":3686043,"id":"Q3686043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"499eae3dabfad935a9c037e5d712a5a419827fb2","datavalue":{"value":{"amount":"+0.91521275","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":"Q640476$6F7A576C-7627-42A5-84EE-CEFFAA4BD106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e2a752c7f2558166996520a2e85a0edf67d3875","datavalue":{"value":{"entity-type":"item","numeric-id":1010960,"id":"Q1010960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3c82e4f9d9d9798e554d3ac1b04061da98dae29","datavalue":{"value":{"amount":"+0.90891004","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":"Q640476$A8254086-CBEF-463B-AE55-BC241CDEB9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08fe3e163f84a2c29df4e4d0ad6cfab7023758d5","datavalue":{"value":{"entity-type":"item","numeric-id":5423564,"id":"Q5423564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2797bfdbb815281ff043476b6b9ca876fdec64a","datavalue":{"value":{"amount":"+0.9083089","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":"Q640476$435324C5-3610-42EE-BC39-A9592EEABE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6a7c0fc0b1f35092f3f39cbedc9ade1796b40da","datavalue":{"value":{"entity-type":"item","numeric-id":3732932,"id":"Q3732932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df815a40e90205d0b3addaf402b12d6e82e22f1e","datavalue":{"value":{"amount":"+0.9049841","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":"Q640476$4EABAF14-6C1C-4387-9E16-72ACEC63B143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cc969db8ca6ba7e25d83e8077b960b5c471e113","datavalue":{"value":{"entity-type":"item","numeric-id":4328063,"id":"Q4328063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c44c97862efca953e712835f97d2bd4b96ee27bf","datavalue":{"value":{"amount":"+0.9039367","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":"Q640476$42FFA017-4F7C-4600-BCDA-8E51929401E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f2933d37a9710d1acb32b7c56d2f000f90850f7","datavalue":{"value":{"entity-type":"item","numeric-id":4293543,"id":"Q4293543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3cf29eb2c101ffb80376a9ef7c6e0767343ed74","datavalue":{"value":{"amount":"+0.89986324","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":"Q640476$AEE74ED8-05A5-479A-B86E-551019FCA105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d31f5c1ae87af856317c98effcc1abcc9e138885","datavalue":{"value":{"entity-type":"item","numeric-id":5286632,"id":"Q5286632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"235f98af84001c1e812ca139b708cca52a5c4302","datavalue":{"value":{"amount":"+0.89956117","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":"Q640476$3F54EE41-2907-4CB0-A61F-887D284383D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15daa5cf85ea88426d1bc6983acef28f4dc74bfe","datavalue":{"value":{"entity-type":"item","numeric-id":4344138,"id":"Q4344138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d4ee198466c2f84e49576cd4e47e9a5861584d4","datavalue":{"value":{"amount":"+0.89655834","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":"Q640476$399BB072-4E56-4CF8-8E6F-FF5A45346E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fd7f8616acfe72e2d521c7acb2445a7f28bb800","datavalue":{"value":{"entity-type":"item","numeric-id":1415059,"id":"Q1415059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4cbd1b37b666dc09aae6656d712c74a50177c23","datavalue":{"value":{"amount":"+0.8907191","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":"Q640476$59FCC6C9-CF9A-44CD-918D-6548E3DB32A5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computability and complexity theory.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computability_and_complexity_theory."}}}}}