{"entities":{"Q1114669":{"pageid":1125418,"ns":120,"title":"Item:Q1114669","lastrevid":42888618,"modified":"2025-07-15T18:12:20Z","type":"item","id":"Q1114669","labels":{"en":{"language":"en","value":"Real quantifier elimination is doubly exponential"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4083591"}},"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":"Q1114669$3FAB1630-A3C1-4440-A09B-214B37C5FF29","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5394fa0a12c95862954d6b55f590c01a8e6719d2","datavalue":{"value":{"text":"Real quantifier elimination is doubly exponential","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114669$4D94D834-49B9-4671-B7CE-C06C4C2E2D59","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1dedfd14b258511f8ac435a59d0b843dd16512c9","datavalue":{"value":"0663.03015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$97D55E17-1965-42D8-85A8-AD90CE1E8BFB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"77568cbbe932fd6f7790026ab28931c09628994e","datavalue":{"value":"10.1016/S0747-7171(88)80004-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$8371CBD3-A9E6-4582-8590-83E8EB2A2282","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a67ebd63c49a2538afe68e2c0f9c56dfc6158b41","datavalue":{"value":{"entity-type":"item","numeric-id":191903,"id":"Q191903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$90F52A20-43DF-4934-AB32-40CDA9772FBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"840c7d35f2ce10026284ad29eddaaaa6e274a32d","datavalue":{"value":{"entity-type":"item","numeric-id":247220,"id":"Q247220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$5418F0D2-C103-4CB4-A2C8-050F19D5DB15","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$9F6788D3-01E6-4253-973D-D1318C979E4E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1114669$E6EFECCB-0A23-4B95-9477-B3B6E1894615","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fbadb0cf00d19209abb1ad4ea57941b60f70b09c","datavalue":{"value":"The authors show that quantifier elimination over the first-order theory of real-closed fields can require doubly-exponential space (and hence time) and show that this doubly-exponential behaviour is intrinsic to the problem. This result has already been proved by Weispfenning by a completely different method in 1985, but the method of the paper is of independent interest.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114669$2A707A2F-084C-404D-8604-4D9BD3D56DD5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d8a223071fe2fd8762483ef53ce76dd67517481d","datavalue":{"value":{"entity-type":"item","numeric-id":807610,"id":"Q807610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$0827116B-8DCB-44E9-870F-6B395DEE1C83","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"176e47af9f9e7cf4ebff07fc1f9e4f94a83134c1","datavalue":{"value":"03C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$0CB116BD-7A99-4DFD-8D24-4DC76B356ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$B079B162-178D-4AA3-BBA8-77D6D04872AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c1435d0ab5d791aa524ff4a1a914fd6a90eedf58","datavalue":{"value":"12L05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$7E51EF21-34ED-4740-898D-FF31BA0B25C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$17E7E665-7653-4D1B-A388-9C0E0366AEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a1448dc8abee9c87d433fb284555380dc61ce707","datavalue":{"value":"12D99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$6583BD61-1B88-44B2-B915-C21060D984A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"502811be0f62fc0fc9ca34a83aa288ffb2771e7d","datavalue":{"value":"4083591","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$3057FFF9-58EE-4F71-8179-B8BE7F65D102","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc63bb2bb3ede85efc7dc55766d36b976469114b","datavalue":{"value":"first-order theory of real-closed fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114669$B4FC9742-C6E6-45BE-B424-2C213855AF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73a97cccd1f884fd46602d4e8a0ed129e1fea3bc","datavalue":{"value":"space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114669$0C00F686-4740-4BE2-8747-F510AA76FFDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19bcfb7b1703083789bbe853b21bd4d5b71c374e","datavalue":{"value":"time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114669$99FDF585-AC60-419E-9CDE-26B7D1129206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac05d112d240e564b5b47ee6b2fb23fde1162d44","datavalue":{"value":"doubly-exponential behaviour","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114669$38EC817A-9430-48A9-B8B5-283AFD491638","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"dd5bf8e54795a92970d946acddd98504388b71e7","datavalue":{"value":"Q56455152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114669$6A9F0718-620A-4578-8037-926385A861E9","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":"Q1114669$CAA9FA4E-6EF1-43D4-926B-4D0F1AAF68A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b35afcacf487f7d4833dfa5c8ec078202260d5c","datavalue":{"value":{"entity-type":"item","numeric-id":1096620,"id":"Q1096620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$BA1476FD-3DAE-471A-9A8C-859F6A8B90E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4d7798eba50e0ffe1e4306d4a4aa338f6be7be4","datavalue":{"value":{"entity-type":"item","numeric-id":4079605,"id":"Q4079605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$6222C6A1-04E0-4FEA-A19D-479D64B07BE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d3441d714d781ca8229c5298590737362f852fd","datavalue":{"value":{"entity-type":"item","numeric-id":1106662,"id":"Q1106662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$91411F3F-7D6E-4898-83E7-907D6A672DFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a5406ea7669ed616e0ac659900417e7fcb90273","datavalue":{"value":{"entity-type":"item","numeric-id":798314,"id":"Q798314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$55258C63-FD94-4138-B898-AECB9EA65A27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8be9375a315209f41df1b38374a5e7e956d28bf","datavalue":{"value":{"entity-type":"item","numeric-id":5807665,"id":"Q5807665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114669$8B9AA8AC-4A49-4465-822F-4647BD8F2881","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec1a05c808bf466dd00f66d61cf3d32549744757","datavalue":{"value":{"entity-type":"item","numeric-id":4247790,"id":"Q4247790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d1ec187204e2daee073aac5b76e31385e8b9950","datavalue":{"value":{"amount":"+0.90199524","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$D05FBACC-D21D-40A4-9ABD-94F3DDC34CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bec6db029688c2c6e40d9f7dc9fc98a396ec1ae7","datavalue":{"value":{"entity-type":"item","numeric-id":868941,"id":"Q868941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2985eb64ce7d86e10eee25849511d0e362355ee","datavalue":{"value":{"amount":"+0.8939197","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$F6FC8D0B-2C35-42E0-A54F-7BE6818FE9FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b108b6ae79eee7fb004b548e83c6e8e74b7859f","datavalue":{"value":{"entity-type":"item","numeric-id":2879136,"id":"Q2879136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec733c955479fc2ae814a9265292b085fa5133c6","datavalue":{"value":{"amount":"+0.8765853","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$8D473798-3E5F-4A6F-BBFD-BD4EDC5950F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40daa8dbea922b25d0fe025f27cc3901edb7b11e","datavalue":{"value":{"entity-type":"item","numeric-id":3419043,"id":"Q3419043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27c0eb9b97ad9b4a1c69c5a16afd69059319cf8e","datavalue":{"value":{"amount":"+0.8732846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$C58DFC9B-16A7-4EBD-86E7-E550CACF29EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e089133e18c337574d39d66e8024f8adc95e7a6","datavalue":{"value":{"entity-type":"item","numeric-id":3758811,"id":"Q3758811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6fa6cf41c9701cdf9583a825a6cdabd7cac54b1","datavalue":{"value":{"amount":"+0.864627","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$ACCE847F-D4B7-418D-BEE7-178A87DC33E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa73079258d345d0d9d3c31e100e3bea98bb65b","datavalue":{"value":{"entity-type":"item","numeric-id":2883815,"id":"Q2883815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20d49e055f754103309557d55af56c5eabc8c809","datavalue":{"value":{"amount":"+0.8573168","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$B06A6A9D-2399-45D8-A49E-84D6A0AC5871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"652e8324c832aee10d0ef8eb458a6b1c4febf6f6","datavalue":{"value":{"entity-type":"item","numeric-id":5447549,"id":"Q5447549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00b1e401b790b3196f6033da2c9c385c76b3c898","datavalue":{"value":{"amount":"+0.8525473","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$F1E4150C-C925-4F13-8FFA-FF9A365D1A47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9599fabc76c44506b389f95a6ca15a74540d2158","datavalue":{"value":{"entity-type":"item","numeric-id":677553,"id":"Q677553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c7494e282e810d15098ac787b5bbe2c96c07cdb","datavalue":{"value":{"amount":"+0.8516513","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$1BC3969B-14EF-4331-B17B-C2740B588306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4db65b1e016d6c6eed73119ae54ff3eed88ab0ca","datavalue":{"value":{"entity-type":"item","numeric-id":4552457,"id":"Q4552457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98e0aeba238ffdf14ac5e3370614df47593f5379","datavalue":{"value":{"amount":"+0.8482602","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$C686DBBE-FFC5-4F62-90A4-3CEF121B1A79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1488344e517f490998946113a8b27a39e41b9289","datavalue":{"value":{"entity-type":"item","numeric-id":5505558,"id":"Q5505558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5ffc836050696f2ecf0f19568ff86c332973553","datavalue":{"value":{"amount":"+0.84713316","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114669$5D3A80F1-279B-4F5E-BA53-2146CF404736","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114669","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1114669"}}}}}