{"entities":{"Q544123":{"pageid":545890,"ns":120,"title":"Item:Q544123","lastrevid":62633430,"modified":"2026-04-11T07:25:04Z","type":"item","id":"Q544123","labels":{"en":{"language":"en","value":"Quasi-polynomial tractability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5907645"}},"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":"Q544123$6929DC33-8D61-42A2-83C6-8B0A5AFDE1FC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"44753da23f0655a37fc1e642d536319d40e6b3c1","datavalue":{"value":{"text":"Quasi-polynomial tractability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q544123$0EA9BAEB-CC86-40E9-AB02-54E90472EE4F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f7ad3219bae92cb97a304d002f9b2277dd27324","datavalue":{"value":"1237.65043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544123$D9C3C8C1-892A-4529-9439-00BF3878499F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5052468658dd4e9614f2e3389bbfa7693a65f63","datavalue":{"value":{"entity-type":"item","numeric-id":486679,"id":"Q486679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$D671A77F-46F4-4ED7-95F5-A8496FA48B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"022cc2ef7a956d48f142cada4328c1d9ba0d76f3","datavalue":{"value":{"entity-type":"item","numeric-id":346289,"id":"Q346289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$27B15244-8536-4561-876E-76E9CAA530B7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$EAF679D2-9873-4770-A396-6DFD3FA0AE09","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"26b2b50ba7a4f5a1aad90db4fa17f9e7a261c738","datavalue":{"value":{"time":"+2011-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q544123$2AC8D10C-8DB8-4097-8FDF-392EA34E1703","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1c11e8f18585c6d92ed7c1724cd049ace9f3b065","datavalue":{"value":"This paper deals with tractability of multivariate problems. Polynomial tractability means that the solution of a \\(d\\)-variate problem can be solved to within \\(\\varepsilon\\) with polynomial cost in \\(\\varepsilon^{-1}\\) and \\(d\\). Unfortunately, many multivariate problems (e.g., all non-trivial unweighted linear tensor product problems) are not polynomially tractable.  It is natural to as for the ``smallest'' non-exponential function \\(T:[1,\\infty)\\times[1,\\infty)\\to [1,\\infty)\\) for which the unweighted linear tensor product is \\(T\\)-tractable. I.e. the cost of a multivariate problem is bounded by a multiple of a power of \\(T(\\varepsilon^{-1},d)\\). This paper considers \\(T(x,y)=\\exp((1+\\ln x)(1+\\ln y))\\), and calls the corresponding \\(T\\)-tractability the quasi-polynomial tractability.  The authors study unweigthed multivariate problems in the worst-case and randomized settings. They show relations between quasi-polynomial tractability in these two settings and for the two classes of algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q544123$86FD61F3-E923-46B6-85AE-00CD0B0A59C9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"72f234120aaa4deef7e0bdb6505da34392bc51a0","datavalue":{"value":{"entity-type":"item","numeric-id":590840,"id":"Q590840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$2415AE95-0EB0-4537-982A-72FCB40E5FF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544123$656CE3AB-1D21-4AF9-A1CA-ECAD735CFB28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fcdcf091e8d296dbd4abc537c837748e635f0d4a","datavalue":{"value":"15A69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544123$C825F2EC-2AD9-4302-82DB-4FE4165165CC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"303aa8485fd97d7ed6e74949051b06ee56462c99","datavalue":{"value":"5907645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544123$6443597E-4F23-4811-8A8C-9E9316D09FC0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d0bc03aa0730e83ce3b77e787baf53230ae3604","datavalue":{"value":"linear tensor product problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q544123$5E2C69DC-0B53-4CA0-AAE7-2AA2F8D4E2DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82838fc85e02786ea6d5c54eeb05f5d2c136d90a","datavalue":{"value":"multivariate approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q544123$EC0DF2CB-58C9-4063-9C58-325C02F4C7D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f87460328507df866ede7716efa2d282ef1a04e4","datavalue":{"value":"worst-case setting","type":"string"},"datatype":"string"},"type":"statement","id":"Q544123$78865CB9-C5DE-4390-AE5F-DF2A7760C195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ec17941d86f5e70578660c2922437461fb93087","datavalue":{"value":"randomized setting","type":"string"},"datatype":"string"},"type":"statement","id":"Q544123$EF79A2CA-A154-4AF6-B14B-9824B84916F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69203d7dd020efd5abe37c3e97efd24aacd66373","datavalue":{"value":"linear information","type":"string"},"datatype":"string"},"type":"statement","id":"Q544123$EF35EE33-B5BA-4F84-9053-CC46998B7A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8fd40ab6ce34cc88d088cef6dcf56473702bdc4","datavalue":{"value":"standard information","type":"string"},"datatype":"string"},"type":"statement","id":"Q544123$DAEF635C-3287-44C1-8AD3-29EE8AC5E2FA","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":"Q544123$A9556CA7-0792-4989-8867-22AFF40A5594","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9f59f3592cb330f331bdb86fadc26a30a30bb088","datavalue":{"value":"https://doi.org/10.1016/j.jco.2010.07.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q544123$3013C857-5268-448B-8F24-0A7FCA1E445A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8c4f8c4d944e3579ab58bdf99cb40101f16abcde","datavalue":{"value":"W2005840206","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544123$E7600F73-E0EC-4E82-85B7-708DB8C4AF61","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e9a47a0840220d2bd6427f27bfbb79b176ee3b3","datavalue":{"value":{"entity-type":"item","numeric-id":883336,"id":"Q883336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$0EAABD4D-5940-4C62-8E40-5C87442EFD95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30c95e6c619e41b3a5ea9e92aa1702b2f97d53f9","datavalue":{"value":{"entity-type":"item","numeric-id":3504234,"id":"Q3504234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$BACA48C7-9E69-4E3E-8203-A4657F49EEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14ee3b0d6712cd99019110ccf3dfefbfa9ede6aa","datavalue":{"value":{"entity-type":"item","numeric-id":839659,"id":"Q839659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$795038A3-3367-4334-A9B9-A23592AF03B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3debc09259614c414fd665abfc07afb5f7e3440d","datavalue":{"value":{"entity-type":"item","numeric-id":1347849,"id":"Q1347849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$8A5D5165-2292-4460-A964-255A16E24B20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bb56dca21878df316e4eaeef3b0d82cf6cc061f","datavalue":{"value":{"entity-type":"item","numeric-id":1772684,"id":"Q1772684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$08C0B045-1A80-48B6-BB59-2D862E39E0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccf28b3887cc8111215e492af9fbef7c89f24bde","datavalue":{"value":{"entity-type":"item","numeric-id":1887111,"id":"Q1887111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$A2761172-8001-4291-A1EC-4A26B5A93846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2fb2239c7beb6b13cc927188f9623a670ed5b3","datavalue":{"value":{"entity-type":"item","numeric-id":5946396,"id":"Q5946396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$1853ADE3-160B-40A4-826C-3201F72F64C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94f0291e6644e8ce8be1c21a1a5f76193c253cde","datavalue":{"value":{"entity-type":"item","numeric-id":940799,"id":"Q940799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$D0D6A856-981F-4F45-837B-BC4FA78E99F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2498ffd8a7ece01dbab10bced6081d8f2ca4c84e","datavalue":{"value":{"entity-type":"item","numeric-id":982085,"id":"Q982085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$A8942720-30E9-4B2A-9E8C-1DAC9ABA1548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b8bac9cc9a698b6a28159f4c35a6874e999325","datavalue":{"value":{"entity-type":"item","numeric-id":731971,"id":"Q731971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$1828F012-59D6-4D6F-AE3B-66297B7CEB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faf1e98f17e1410c28a20c74dcf390e7440c1a01","datavalue":{"value":{"entity-type":"item","numeric-id":3993279,"id":"Q3993279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$A3D39F78-507C-45ED-B32C-68B8B169874D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"948accf54a68f21e298fc9570a797d717c8a7e29","datavalue":{"value":{"entity-type":"item","numeric-id":1881675,"id":"Q1881675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$3D4CF684-55FE-4298-9AB1-80DD1007FF14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"158c850b7d1a63f1ecf1337e9fbeb149cb92b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":3426031,"id":"Q3426031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$31BC06C3-5545-45B4-AFCA-790FBC96FFDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7319997c16013b7d3ee88e79dcee6841207f6759","datavalue":{"value":{"entity-type":"item","numeric-id":1319354,"id":"Q1319354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q544123$22F6DBC8-2AF2-4DBC-975D-102B679AB7A3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2194bd521fbfebeeae5071b17cef62b057a49f0e","datavalue":{"value":"10.1016/J.JCO.2010.07.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q544123$6E9F6463-702E-44C7-8D50-73D4FF463232","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d61bc3b748632c4cdbc6d38a4f05e0b4e462ac4b","datavalue":{"value":{"entity-type":"item","numeric-id":4611835,"id":"Q4611835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e9c50d561e80d78e571a597b6856b8f4b320dc3","datavalue":{"value":{"amount":"+0.8759557604789734","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":"Q544123$B6558DB2-70B5-4111-A664-E95EADC2A161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0acf66821adb6ec85cb4cf20f51081a954db629a","datavalue":{"value":{"entity-type":"item","numeric-id":883336,"id":"Q883336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6b3406819e7eb48207b56148cef94a4f3ca3b06","datavalue":{"value":{"amount":"+0.8717018365859985","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":"Q544123$8F19642E-1B48-4B51-B476-132DF69E6A68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bba3b2e77f32c501b2878550cfc9f65122371dee","datavalue":{"value":{"entity-type":"item","numeric-id":880024,"id":"Q880024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98169887356c4ba46825d58a7f9a7a35fd336bad","datavalue":{"value":{"amount":"+0.8657014966011047","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":"Q544123$C48E38E5-BBAE-47AF-B3E8-D51917E4824B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a66031cacd2dc97d984b2ee5c8d950c1b1b752d6","datavalue":{"value":{"entity-type":"item","numeric-id":839659,"id":"Q839659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faf69f646fd0db295b072d6169f2c6f1ca9335a4","datavalue":{"value":{"amount":"+0.8628438711166382","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":"Q544123$A0C00944-3FF1-4074-ADF7-6254E14A8201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d121c2710e1aff5c0fcc82a6448a9e084895025","datavalue":{"value":{"entity-type":"item","numeric-id":2509949,"id":"Q2509949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f26782db4231cb813b1c82566d2a0cdb8d46ab2","datavalue":{"value":{"amount":"+0.8535925149917603","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":"Q544123$21EFBD0D-4FE2-4B50-A426-B17EA030ADF2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Quasi-polynomial tractability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Quasi-polynomial_tractability"}}}}}