{"entities":{"Q1308646":{"pageid":1319396,"ns":120,"title":"Item:Q1308646","lastrevid":67518210,"modified":"2026-04-12T18:32:53Z","type":"item","id":"Q1308646","labels":{"en":{"language":"en","value":"Complexity and decidability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 464566"}},"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":"Q1308646$94CC4C2B-C0E6-4F39-BFE7-573CF5BFF8DF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0d279455e62c7ff2a233f97ba187e63f99f0c1e3","datavalue":{"value":{"text":"Complexity and decidability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1308646$560979D1-5DD9-4B02-9334-A69FED2E99BF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"496bba1e912ba663669f84b281912e83c0b6de8c","datavalue":{"value":"0787.03030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$63B52B02-52B7-4368-B6D2-775473DFEB46","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c06aa3c4dc97754b3a90c94fdcbba2fb94420c5","datavalue":{"value":{"entity-type":"item","numeric-id":185419,"id":"Q185419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1308646$82D2EDBC-3409-49DD-A513-69DCEDC411C6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3f0402d8a7fa11b3a8941089edab76117ab371d7","datavalue":{"value":{"entity-type":"item","numeric-id":229877,"id":"Q229877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1308646$6B30B353-F1DE-4B58-813C-20E46C389864","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7c693d8520cbbc96b063ad4da4a2b180187c6171","datavalue":{"value":{"time":"+1993-11-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1308646$CEAAA710-955D-46FE-A450-3DAFB3C32FCD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"06fcb065f6859434d34cb565b966a88e02ffc655","datavalue":{"value":"This book is the supporting text of the course taught by the author at the University of Caen. It includes main results in complexity theory concerning first-order logic. The author emphasizes on the main negative results concerning the complexity of Boolean calculus, first-order logic and of arithmetic. The theory is presented in the standard model of Turing machines. The model is largely studied in the first six chapters of the book. Thus, the reader may not be familiar with complexity and even logic theories. We note the elegant manner the author succeeds in giving a rigorous and at the same time easy to understand presentation of some difficult results.   Here are the chapters of the book: 1. Algorithmes et machines de Turing, 2. Simulation d'algorithmes, 3. Changement de r\u00e9pr\u00e9sentation, 4. Fonctions r\u00e9cursives, 5. Machines universelles, 6. Machines non d\u00e9terministes, 7. Complexit\u00e9 du calcul bool\u00e9en, 8. Complexit\u00e9 des logiques du premier ordre, 9. Complexit\u00e9 de l'arithm\u00e9tique, 10. Complexit\u00e9 de l'addition des entiers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$D9757849-77AF-4E03-B1ED-F7683894F926","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$10C8DBA0-2FE4-473A-8972-521F41AB1E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5eb59e57cdf22dd229e0d8b292a33dd322f6e9d4","datavalue":{"value":"03-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$11CF967E-1B69-4D78-8ABC-5B443E05919E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"98c5206e338942c77451c20a9a5ffe8ae1a4cf18","datavalue":{"value":"68-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$B6462A4B-E04C-4420-8055-142BE110ABC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$15C86BEF-2CD6-4B84-B2AF-5549127866D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$04E78DAE-84F4-4170-AD1A-FF25FCA54E56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$39A2164E-E097-427B-AEF9-94AEF9162A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$CD8D23FC-64F2-4ED4-9B40-A89BCA0DE446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$7A81E352-5999-44D6-9211-1DA79207884B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$E38525F7-718B-4D0C-8B4D-BBCCE4F87EAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$F96A5E2D-6C46-4F91-9B91-F75BC227FA49","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b2c4087345184fc908b353b220ce4d0e9d0c695","datavalue":{"value":"464566","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1308646$E527DA62-AC38-478C-9456-5DE42B3B64EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$628374D9-55A5-454E-BE4A-AF8247D5BFDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c92f25b9ea895f2b57606a79389bb66216727043","datavalue":{"value":"recursive functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$3554605E-628D-4DD3-A2AA-679359D5B453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$B89DFA5C-6B4D-45E3-8131-D1B9346C6739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11acd2fb6ad6c566c252aa4b6fd795400412f6ca","datavalue":{"value":"complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$5D8192B1-FE12-4E00-9B7F-51ADEB233E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23d0f6a1d37851bba753061553467bb22ec5504c","datavalue":{"value":"first- order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$736C1F32-3725-4710-A50E-61427F56E006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd9e3b9fe7c361bc76e3eae839a5f50f3c683174","datavalue":{"value":"Boolean calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$C3C08742-12D0-484A-8084-3BB7D353989E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be1268b65fc1d6781eb5c0f1073a98e5cb46f217","datavalue":{"value":"arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$B21AC7B3-F1F6-4A23-91D8-025DFDCCAEB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1308646$5953D4D1-FB89-46FF-8604-517FEFF22A5E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e5adb2f5b9beef2201bef72e73c6f511c159db61","datavalue":{"value":{"entity-type":"item","numeric-id":493519,"id":"Q493519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1308646$9553A47A-3DFB-4F54-BA01-54D606C4FC94","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":"Q1308646$CC6A1552-539B-4F5E-80D3-E7CA1296F1E7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f94ae3bcb9061d64d89425e0c03d5c09688fff08","datavalue":{"value":{"entity-type":"item","numeric-id":3722466,"id":"Q3722466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2603e2bd60287bab16e9042a5e40dbb9437bf9f2","datavalue":{"value":{"amount":"+0.8302072286605835","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":"Q1308646$390CCF27-D6F7-4BC7-A408-A0E41016B222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22c378c946fc5b90b9f5875ad658232a6b6d5228","datavalue":{"value":{"entity-type":"item","numeric-id":4877500,"id":"Q4877500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dc21137ca75ce20f0d949bb322bea949b96447f","datavalue":{"value":{"amount":"+0.7766546010971069","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":"Q1308646$EDDBB8DF-636C-4D2F-BEE1-E958AEB5687F","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":"f3843cbc28cce4f786f2c0462e04d1ebef11ff21","datavalue":{"value":{"amount":"+0.7653829455375671","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":"Q1308646$0FC31BA4-24E2-4833-ADD6-FC0509014B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aec3ff74c571ea528dc942662ff1c615bf8682a2","datavalue":{"value":{"entity-type":"item","numeric-id":3159146,"id":"Q3159146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1eecc76079b53e75ac76954f12855f2a9bf10cf3","datavalue":{"value":{"amount":"+0.7616628408432007","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":"Q1308646$9AAFB33B-4388-41A0-B129-F3C80A227788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bec0c4844ee35e7f35f23a30a385ddb41de3fec7","datavalue":{"value":{"entity-type":"item","numeric-id":5691140,"id":"Q5691140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f86babe3b142120d423e9dc22c9c4ee10e105b22","datavalue":{"value":{"amount":"+0.7615861892700195","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":"Q1308646$91FAF118-B6B9-4403-9ADB-854CCE793A60","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity and decidability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_and_decidability"}}}}}