{"entities":{"Q2272156":{"pageid":2282899,"ns":120,"title":"Item:Q2272156","lastrevid":43797597,"modified":"2025-11-14T11:45:59Z","type":"item","id":"Q2272156","labels":{"en":{"language":"en","value":"Approximation of infinitely differentiable multivariate functions is intractable"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5590653"}},"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":"Q2272156$E8C76409-85F0-425B-93E3-A31E0BFFABEE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"70b1578a7be057662b7073d8606a017153ac4789","datavalue":{"value":{"text":"Approximation of infinitely differentiable multivariate functions is intractable","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2272156$AA46EED3-6948-4C7E-8B2B-3C2DF914C3D0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"170aa2abed5bed278e881cdc5773fef4486a0e34","datavalue":{"value":"1180.41031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272156$AD32A102-EC9D-40F6-8D18-6535C675FC54","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":"Q2272156$2B1C2A68-58F1-4299-A93D-6F07A814136C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"22fa6455513bb7f53a1cef7bcfc7a401b9bebc8a","datavalue":{"value":{"time":"+2009-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2272156$06C68022-7317-4432-98B9-68488D60FC9A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e882863f747516ec8121ce81e4ef7357cf11b494","datavalue":{"value":"Let \\(F_d\\) be a normed linear space of functions \\(f:[0,1]^d\\to\\mathbb R\\) that are infinitely differentiable endowed with the norm \\(\\|f\\|_{F_d}=\\sup_\\alpha \\|D^\\alpha f\\|_\\infty<\\infty\\).  Let \\(A_{n,d}(f)=\\varphi_n(L_1(f),\\dots,L_n(f))\\), where \\(\\varphi_n:\\mathbb R^n\\to L_\\infty ([0,1]^d)\\) is a linear or non-linear mapping, and \\(L_j\\) is an arbitrary continuous functional whose choice may depend on the previous values \\(L_1(f),\\dots,L_{j-1}(f)\\).  The worst case error of \\(A_{n,d}\\) is \\(e^{\\text{wor}}(A_{n,d})=\\sup_{\\|f\\|_{F_d}\\leq 1}\\|f-A_{n,d}(f)\\|_\\infty\\), and the \\(n\\)th minimal error is \\(e(n,d)=\\inf_{A_{n,d}}e^{\\text{wor}}(A_{n,d})\\).  The minimal number of information operations needed to solve the problem to within \\(\\varepsilon\\) is \\(n(\\varepsilon,d)=\\min\\{n:e(n,d)\\leq \\varepsilon\\}\\).  A problem is weakly tractable if \\(\\lim_{\\varepsilon^{-1}+d\\to \\infty}\\ln\\,n(\\varepsilon,d)/(\\varepsilon^{-1}+d)=0\\), and intractable when the above relation does not hold. If \\(n(\\varepsilon,d)\\) depends exponentially on \\(d\\), then it is said that the problem suffers from the curse of dimensionality. Moreover, a problem is polynomially tractable if there exist \\(C,p,q>0\\) such that \\(n(\\varepsilon,d) \\leq C\\varepsilon ^{-p}d^q\\), for all \\(\\varepsilon \\in (0,1)\\), and \\(d\\in\\mathbb N\\).  \\textit{F. L. Huang} and \\textit{S. Zhang} [J. Complexity 23, No.~1, 73--81 (2007; Zbl 1108.41024)] conjectured that this \\(L_\\infty\\)-approximation problem is not polynomially tractable, and this paper is devoted to prove this conjecture and somewhat even stronger: the problem is not weakly tractable. The result is the following:  For this problem \\(e(n,d)=1\\) for all \\(n=0,1,\\dots,2^{[d/2]}-1\\). Therefore \\(n(\\varepsilon,d)\\geq 2^{[d/2]}\\) for all \\(\\varepsilon \\in (0,1)\\) and \\(d\\in\\mathbb N\\), and \\(L_\\infty\\)-approximation is intractable and suffers from the curse of dimensionality.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272156$748F7B64-1E9A-47B2-8226-54F088DE1733","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"89346f20a6c5c6b864a211d37f17719b2851c4ad","datavalue":{"value":"41A65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272156$E5B090AC-323D-4E26-AAF7-53502B14CDF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dbe7739c02784b5dbd4723e3101dc4f5f70dec58","datavalue":{"value":"41A25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272156$AF6739FC-7BEB-47B1-AE17-75EA65CD88DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fb3a8bd6d20cd71ea48713e39f04a71a6d560116","datavalue":{"value":"41A45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272156$F747E727-8BF9-43A8-A345-219487309E8B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9ddbc2d57e9e4988f3676ef2259d192067101ce1","datavalue":{"value":"5590653","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272156$8FE0CC18-9246-4AC6-BEC3-66B67E66A183","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88ffd2ca9452a95455f19f35bfb3f100bed2aeb1","datavalue":{"value":"tractability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272156$84CEFE66-0EC8-4A0E-91D7-88D1C1D8D957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef35c379d5a015d2c5520654beb2e1c33ab3e024","datavalue":{"value":"curse of dimensionality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272156$594E1AD5-0BF4-4C2A-BAC3-79939628D194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5097db38d6dca97fdfc6bc38bcb12c7dcfbf08b7","datavalue":{"value":"rate of convergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272156$455509E0-9703-4924-B959-C74FCF3745DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d6660a6b81be378e63921f896a19bce7d79d81b","datavalue":{"value":"approximation of smooth functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272156$E4C0B675-944F-4508-A9D3-9EA405054BC2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6018a2a53dcc745eb502de825d121b26a76b54f3","datavalue":{"value":{"entity-type":"item","numeric-id":192022,"id":"Q192022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272156$561DB6DF-7061-4B00-8FCA-28D41494CA52","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":"Q2272156$8C550973-CE8D-487E-88CC-0E917E9F7178","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7ffa677918b324f746f69da6d13c929a6e1ecddd","datavalue":{"value":{"entity-type":"item","numeric-id":426996,"id":"Q426996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272156$E9689207-7DEB-4592-B028-E965B3D3ECCB","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":"Q2272156$44A448DF-D119-41F5-B4A8-785D6B98A12C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bc963a62995652c0d187307125f9d1209ea66bd4","datavalue":{"value":"https://doi.org/10.1016/j.jco.2008.11.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q2272156$A460854F-EA66-4999-AD67-B76FE86CE142","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"78d3f826f4587dc11280cc823e3594971efb393c","datavalue":{"value":"W2075646404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272156$1F9878E6-AE84-427D-9B94-E158F213DE01","rank":"normal"}],"P223":[{"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":"Q2272156$DA1B749C-D7DF-4AA6-9B09-1C5A06520624","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fab4cf399e350bff077a96de33e7798c4c145ece","datavalue":{"value":{"entity-type":"item","numeric-id":870341,"id":"Q870341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272156$507AB221-A9E2-47C4-B237-0B3269B2B91F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f5e73b7778e3c4dc8c50571b07049b8f4590beb","datavalue":{"value":{"entity-type":"item","numeric-id":843721,"id":"Q843721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272156$6A1B0A67-AF19-46F6-B650-E0FA3D779BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ca72e6f11186c0ffb2f62fe725ee9d11ac38ede","datavalue":{"value":{"entity-type":"item","numeric-id":843723,"id":"Q843723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272156$224317AD-515C-4673-8E16-A94D7D3C7373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fc459087ddedc6f015c556073647203761bd744","datavalue":{"value":{"entity-type":"item","numeric-id":4340859,"id":"Q4340859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272156$A4E4B7B6-C664-4131-862A-6EAF8BD58D5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f884556a641071aa85debaa5b2d09875c77e51e","datavalue":{"value":{"entity-type":"item","numeric-id":1402005,"id":"Q1402005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272156$6FD894FD-02D6-424F-A3FF-10A11CAB5255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a081291e7ba559bc54a213eb5fee089c91ed2e93","datavalue":{"value":{"entity-type":"item","numeric-id":1426049,"id":"Q1426049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272156$D61A2956-084E-44DA-8C16-15FD41EE405E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"08f5964524ddc0879a521e0860c36b998f536832","datavalue":{"value":"10.1016/J.JCO.2008.11.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272156$DAAD4C7F-B094-4018-9EBC-246A4FD8C9F0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40141fba523bed896da6f5ff67a7187211b17625","datavalue":{"value":{"entity-type":"item","numeric-id":870341,"id":"Q870341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9791995ae9a97b14fc40663f13317fa3ce34a43","datavalue":{"value":{"amount":"+0.9669507","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":"Q2272156$4BCFC391-C390-4316-A96C-209836024D1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ca12ba6e47288ee93e821c667f2ae12861987d5","datavalue":{"value":{"entity-type":"item","numeric-id":5905514,"id":"Q5905514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca9d06bdd3b2c5079e194334e97e21e4c93239f6","datavalue":{"value":{"amount":"+0.8910985","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":"Q2272156$CD02F911-65E2-4F9A-8A23-A6CC8BDC94B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17dcaf4f9479d6d218cabcc5869d235444c93582","datavalue":{"value":{"entity-type":"item","numeric-id":5894713,"id":"Q5894713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca9d06bdd3b2c5079e194334e97e21e4c93239f6","datavalue":{"value":{"amount":"+0.8910985","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":"Q2272156$CB7E659A-313D-4C14-A6A8-DD28B0080C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68b563b2fa2a6754931bc2f072a616a9e759ec04","datavalue":{"value":{"entity-type":"item","numeric-id":1668070,"id":"Q1668070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66d31f0994863dba166e1f3922c04e0d58764a77","datavalue":{"value":{"amount":"+0.8861641","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":"Q2272156$1E66A319-CB78-42FA-A01A-E0AEC3439D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55f0c1a3af445c87c9f1401a98a0e2b373de40ca","datavalue":{"value":{"entity-type":"item","numeric-id":2442807,"id":"Q2442807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd7aaabc716927b3c25a51b2dc10d190ca44c7e4","datavalue":{"value":{"amount":"+0.87934065","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":"Q2272156$4C96B25C-BBBD-44CA-AD5E-A83C5A3ED2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37e51b4e1f64c0769345154b2c199e095b71d22a","datavalue":{"value":{"entity-type":"item","numeric-id":1116026,"id":"Q1116026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"229ca3c0b1847c52934ce60c6d9d86aefa64dd53","datavalue":{"value":{"amount":"+0.8758501","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":"Q2272156$BB0B3271-A027-4901-A0CE-E983C2BDEF30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9af366a1f2f2dc72ce02298b10812c456657b794","datavalue":{"value":{"entity-type":"item","numeric-id":5493121,"id":"Q5493121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dde2a11a9951f94a0fc983ef0408d1979678dfe","datavalue":{"value":{"amount":"+0.8730827","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":"Q2272156$188F6251-3875-4B7B-80CA-D3CEC229363B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df6b637aa3c96fb5a69ae748e4b2d072ed6dfdb1","datavalue":{"value":{"entity-type":"item","numeric-id":810793,"id":"Q810793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b36138fb7535b8e47bc4b052b2788cbd8dd10134","datavalue":{"value":{"amount":"+0.8702327","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":"Q2272156$1F3C26E9-A4D3-4242-BD1C-40DDE2A277E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"243f14737f146278e49525623c014eb9aadc25bb","datavalue":{"value":{"entity-type":"item","numeric-id":4716673,"id":"Q4716673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0c6d22e84dfd72eb0a9bfc6064b9ee0c8fc31b0","datavalue":{"value":{"amount":"+0.86317706","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":"Q2272156$1786944C-46B6-4148-A1CA-556649C38047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a34cbb158d8c546458a2c854104c8a8a8f5999d","datavalue":{"value":{"entity-type":"item","numeric-id":4309656,"id":"Q4309656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d383668f83b723d5659ce1c2779a818bdeacf621","datavalue":{"value":{"amount":"+0.8622977","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":"Q2272156$1EF4123A-AC99-4F16-B66C-676038555A70","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2272156","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2272156"}}}}}