{"entities":{"Q1113939":{"pageid":1124688,"ns":120,"title":"Item:Q1113939","lastrevid":77840276,"modified":"2026-05-06T10:10:29Z","type":"item","id":"Q1113939","labels":{"en":{"language":"en","value":"Solving systems of polynomial inequalities in subexponential time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4081676"}},"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":"Q1113939$74239D27-289F-4313-816A-703974BFB823","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8632354ffaa0ef9b80b4b5e58414131c1d4b5e4d","datavalue":{"value":{"text":"Solving systems of polynomial inequalities in subexponential time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1113939$159F5D55-06CD-4BE7-B760-1B2794CA8492","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7d794c34d2518022b0a8c3e3c010696bff331db2","datavalue":{"value":"0662.12001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$CD046F87-9BD4-46C4-86DD-3498E1E9976C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dc3a87957036f90336d39febd730057e27196551","datavalue":{"value":"10.1016/S0747-7171(88)80005-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$84A5EBE1-C2B5-4682-80D2-3874077B698D","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":"Q1113939$8BB7038E-865D-4526-9039-DFE88C402044","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":"Q1113939$E5250C76-EC7B-4A5B-8B93-C89AE76ED4E7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a47cd682bb2eded624e9548935347a5528991030","datavalue":{"value":"The authors developed a subexponential time algorithm to find real solutions of systems of polynomial inequalities. A method of finding real roots of a polynomial was introduced as a starting point of the algorithm and the general case was reduced to this case. Theoretical background of the algorithm was given in details in the paper while a general outline of the algorithm was provided. The algorithm has a running time bounded by \\(M(kd)^{n^ 2}\\), where k is the number of polynomials with degrees less than d and coefficients not exceeding \\(2^ M\\), n is the number of the variables. The previously known upper bound for this problem was \\((Mkd)^{2^{O(n)}}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113939$411FA08A-8AC9-4B9F-96CD-368FED9F9375","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfeaad0862a23378a3c738963be2d25d4928c7a1","datavalue":{"value":"12-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$E59BAFA7-1BB4-4860-B3CA-D9D2BFE72806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$BA0E3F64-B09E-4352-BC0E-F7ADAE9E8C9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"299c2ceee90a97db4ef5b7d633c2a5784e0cb3c0","datavalue":{"value":"12D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$57FFF1BC-BB0A-45B8-87CD-F555E275F75F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"80619583a343f6ab8e0090f36b890511a86ef408","datavalue":{"value":"14Pxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$693276D7-2FC6-4787-ACCA-01FFBD5795FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"75b5ae7d63c4b2ff3513743a5ea9e7be306e24ac","datavalue":{"value":"11R09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$4288A63D-8AFC-4B80-BC4E-AA2AD61BBAEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$8714C1C6-2D05-4C6D-BF4E-68322F75E1A4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c198db06e9b6c3247cf438a755255e02a5aea9b3","datavalue":{"value":"4081676","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1113939$F2FEB08D-1BDF-4367-984C-41FC5585809F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010c7d2ed2de24e1d8a535188cc19c40627ba1be","datavalue":{"value":"algebraic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113939$FE834293-FA93-4F2C-9D91-463638D99855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb200adc9efcab28807ceec53496262758856949","datavalue":{"value":"subexponential time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113939$80A03D7F-4A6B-4A92-A7E7-3F9604C1B620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae455c46658279b19fc4709c25768acf4fd48602","datavalue":{"value":"real solutions of systems of polynomial inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1113939$CBE0915B-9626-4983-B172-DEF336F35948","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a4a79399764b502030de9c1fe7fb099f6c796d65","datavalue":{"value":{"entity-type":"item","numeric-id":1583885,"id":"Q1583885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$F7884347-2628-4634-9F93-4C83B60D9509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b80574436eb2cfe6e06d2d1b3446d5365a842cc","datavalue":{"value":{"entity-type":"item","numeric-id":1190746,"id":"Q1190746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$BD3FA9EF-071A-44C9-9C94-CFA19FF697AE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2c1547f7c74ead62529212a4b955a0cba891fdee","datavalue":{"value":{"entity-type":"item","numeric-id":1064349,"id":"Q1064349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$346A0295-2233-404A-94D9-450412C4DCA5","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":"Q1113939$1F33F766-2885-40DF-A371-C6EF5CFBECE0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c21355d631011ed037f0c70ab644c2ea5c134703","datavalue":{"value":{"entity-type":"item","numeric-id":4747509,"id":"Q4747509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$5BE2D603-9E3D-41A6-9019-0382C8922C0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fa745fed236513fb52d9febacf8c197e209a16c","datavalue":{"value":{"entity-type":"item","numeric-id":3728104,"id":"Q3728104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$67C0729C-0433-4ED2-A6A3-9173208E9498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f1139f87ae775ef65a114512a6abaadba3bdc67","datavalue":{"value":{"entity-type":"item","numeric-id":5184990,"id":"Q5184990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$DB154C31-4CAF-4740-BC48-EC5C0AC6A87A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bc0d7c2f9fbebdd682ae380725d8093d2d4a292","datavalue":{"value":{"entity-type":"item","numeric-id":5187264,"id":"Q5187264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$8BE5E708-EAD1-4920-9878-15ED4EE9B190","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":"Q1113939$658782DA-4959-4FAD-893D-19F786922702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c451625003fa8ec403d3e1a215907cec62a72c9c","datavalue":{"value":{"entity-type":"item","numeric-id":5184991,"id":"Q5184991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$6D77E876-7CB9-4C1B-932B-AF5C58F90DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7a32ed3ebe2a6943b21f5610ce09de81d64f5fd","datavalue":{"value":{"entity-type":"item","numeric-id":3820004,"id":"Q3820004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$B1DA0F99-7E27-4BF2-BFA7-A865717A84D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94af4b398439d78f99f728572ea461069cbeaa2e","datavalue":{"value":{"entity-type":"item","numeric-id":5633582,"id":"Q5633582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$CD75A877-E6B8-48BB-9587-18DE3AC524E4","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":"Q1113939$2D10F5DA-3190-4220-909B-D44BFEAA45A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97236fbeb6b6b2bba840114a8ba2f0448b9619f9","datavalue":{"value":{"entity-type":"item","numeric-id":4197641,"id":"Q4197641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$400106E0-6BE3-455E-90F9-F1DF6295011C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6899b40a48bb6dd55553fc9b55d2ab3a1166c63","datavalue":{"value":{"entity-type":"item","numeric-id":5588717,"id":"Q5588717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$BC63E26A-6BDA-406E-9697-F67C33D5D943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eb5d7dec27c8818f722e687ece5f845ee917c3f","datavalue":{"value":{"entity-type":"item","numeric-id":3684200,"id":"Q3684200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$649C5C13-210A-4AE3-91CD-5F47A89E9ED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b515ced739c6c8e682cf74e7321d82d15295643","datavalue":{"value":{"entity-type":"item","numeric-id":5736681,"id":"Q5736681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$CBF6F198-66A2-4A74-82BE-9E6525917146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a17cc579f26d7ae30e34c9812f79d3304103453","datavalue":{"value":{"entity-type":"item","numeric-id":5510566,"id":"Q5510566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$098A6A5D-5CC7-4738-8D4A-21B5A883F44B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b7afcb9a0497959937cf113b16fb13499994cb9","datavalue":{"value":{"entity-type":"item","numeric-id":4053736,"id":"Q4053736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$27A8ABD7-ED6A-4C31-BD25-0F79375832A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82d5ab76b12c558c2b19763ca1807402cbe3af0c","datavalue":{"value":{"entity-type":"item","numeric-id":4771357,"id":"Q4771357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$819A2A52-9B04-427E-8142-09A481CB2E81","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":"Q1113939$8679D60F-9354-42B4-93BA-8CFAAF9F678F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88be1e1c8c73530cc3ddca1d615c0e260ae28e63","datavalue":{"value":{"entity-type":"item","numeric-id":4189745,"id":"Q4189745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$611F7245-7398-45D9-A2A6-2BF022C0B0BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62b68d8b5473671367b1a9db94afd39aa610e805","datavalue":{"value":{"entity-type":"item","numeric-id":3336589,"id":"Q3336589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$DE06C9C8-5F35-41F8-A1CA-23EE01001880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4b12d8b6db4861de194e04359d968f46f56d4ca","datavalue":{"value":{"entity-type":"item","numeric-id":3746798,"id":"Q3746798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$FC0273AE-B187-468D-919E-1057F5CCDF5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e92de3f05590685578d3ffc2c8aee29bbdd76883","datavalue":{"value":{"entity-type":"item","numeric-id":4137157,"id":"Q4137157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1113939$8EAD1BFC-8F43-48CE-AB72-77DF2F157BED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69f6f7e5e279533b4b93d690284fb15fb0121100","datavalue":{"value":{"entity-type":"item","numeric-id":3746798,"id":"Q3746798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9c4e8af917b69caad4b68f9f81b339f5a15d498","datavalue":{"value":{"amount":"+0.9234282970428468","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":"Q1113939$AFB84722-84D1-4BA5-A400-3F321F97D9FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4319ec31dc275600192af31a78bfe0d327f78b1e","datavalue":{"value":{"entity-type":"item","numeric-id":4733314,"id":"Q4733314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19329afdb4ea32982a37c401d0a3adf7379a3058","datavalue":{"value":{"amount":"+0.916320502758026","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":"Q1113939$C0193AFF-3A6C-45D4-9B79-3FA092E4D56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d39b595bd45a04d5ae115b869fcbb38847d4fe10","datavalue":{"value":{"entity-type":"item","numeric-id":3485804,"id":"Q3485804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4912a728e782627db98bcec1e0d5411b50896172","datavalue":{"value":{"amount":"+0.8474787473678589","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":"Q1113939$7C46B7CA-1532-40F1-961E-724BC883107D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fad7874ece3ff5e22d33ca1837090249d395539f","datavalue":{"value":{"entity-type":"item","numeric-id":3973352,"id":"Q3973352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f2533cb841b9cdcbc0c17d3909060338fdbf655","datavalue":{"value":{"amount":"+0.8356130123138428","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":"Q1113939$200F987B-812A-49B9-89F0-A5D62DD9F509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a50776fe04d9b9d87b5ed820adc2db9661f4904","datavalue":{"value":{"entity-type":"item","numeric-id":1976673,"id":"Q1976673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45c3e1bda8fba0a449b3bdec8e2c6aa6f6c51932","datavalue":{"value":{"amount":"+0.8324697613716125","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":"Q1113939$909D418E-3E70-4685-B944-ECDD160250A2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving systems of polynomial inequalities in subexponential time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solving_systems_of_polynomial_inequalities_in_subexponential_time"}}}}}