{"entities":{"Q1821775":{"pageid":1832517,"ns":120,"title":"Item:Q1821775","lastrevid":73385442,"modified":"2026-04-14T15:43:14Z","type":"item","id":"Q1821775","labels":{"en":{"language":"en","value":"On the computational complexity of best Chebyshev approximations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3999920"}},"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":"Q1821775$81434FD9-5828-4BDA-BA7A-0BDD6BF4F99B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"148c925e0dcc410cfbefd879f9d7646c8c9f4b59","datavalue":{"value":{"text":"On the computational complexity of best Chebyshev approximations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1821775$701584E5-9D01-4E56-A609-FB9BF4AF18EE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c0ace8c6d638ecffb7cff9618a9a67d18c9480f7","datavalue":{"value":"0617.03039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821775$62B2414A-3E00-4456-B241-F5C1CD015594","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ef657b32918351b796866c0656de867276688b97","datavalue":{"value":"10.1016/0885-064X(86)90014-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821775$B23C0F7C-6A14-4243-996B-A842A6DCC353","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":"Q1821775$E0BE9BE0-A6B6-4EC8-A3B8-DF49A23009A8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1821775$02BB1032-EAD5-420F-826E-442C3A417194","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b06bdabb11bdf522be30a0fd1606c96c97ca537d","datavalue":{"value":"The author defines a formal model of computation of real variable functions (using binary strings to represent real numbers) and investigates a series of problems concerning the best Chebyshev approximations of computable functions on [0,1] from the complexity theory viewpoint. Let \\(POLY_ n(R)\\) be the set of all polynomials with degree n and rational coefficients and let f be a continuous function on [0,1]. Let \\(E_ n(f)\\) be defined as follows:  \\[  E_ n(f)=\\min_{\\phi \\in POLY_ n(R)}\\max_{0\\leq x\\leq 1}| f(x)-\\phi (x)|.  \\]  If f is a polynomial-time computable function, then the sequence \\(E_ n(f)\\) is shown to be NP computable. If \\(P=NP\\), then for a polynomially computable function f on [0,1] the sequence \\(\\phi_ n^*\\) of the best Chebyshev approximations is polynomial-time computable. A series of other theorems of such kind are proved. The paper contains a series of open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821775$1FC00A63-C903-4F1E-B38C-A2CAB97F5234","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0282342b24b585fa878a09dabeb8eb52c72be5a3","datavalue":{"value":"03F60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821775$27A6F33D-81A7-4FDF-8DEC-4BA501C6F027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821775$31364A81-97A0-495B-BCD0-F406F18F36F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e8aac6473e24fd89a35b72e2e3af4914f3103ed","datavalue":{"value":"41A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821775$9280D31C-0CE6-49E2-8DBF-AD0BCEC8E61A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821775$E47D238D-4FFE-4827-97EC-337E1819A107","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"72110e277c6926357ff218335359555222f80ba1","datavalue":{"value":"3999920","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821775$B5B5BE3C-62EA-470B-B53A-340CE1D18FED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf692e68674d83a3c4bdb70ab12748a2b41d6d8d","datavalue":{"value":"formal model of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821775$0E61D334-74E0-460C-ADBC-862929B9767D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19b210111cdbc71209eb436c23741f1133071a65","datavalue":{"value":"best Chebyshev approximations of computable functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821775$247B6677-25B0-4D03-9347-0F91EEF25AF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e6fef79d781284909ec93a485678c7408e58583","datavalue":{"value":"polynomially computable function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1821775$AB9592A3-210B-4663-9CB5-CFAF5D2C40F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"13bc86079a0769c5ab1c6f28dc4e52a39f4a573a","datavalue":{"value":{"entity-type":"item","numeric-id":1295380,"id":"Q1295380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$52F79EB6-0DD7-42B6-B1DC-F9C4647E2E9A","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":"Q1821775$3E7E7211-EAC4-4055-85E7-3D6D726F1EDD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2edb40cd56d96e7aecc58a089d38006419275f68","datavalue":{"value":{"entity-type":"item","numeric-id":3319163,"id":"Q3319163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$AC3D48B0-B52B-4D1D-BD05-E9E55636D85A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"569fa9c504c5ecc928a3de3b9e903ccaa7770887","datavalue":{"value":{"entity-type":"item","numeric-id":1057267,"id":"Q1057267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$103AF282-4D63-4AE8-8D4D-0EFE5B6EF576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$A7046D76-579C-4093-9FC6-211BF25D1A81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24d0e4934f532477eeee9b0eb15120638c6eea58","datavalue":{"value":{"entity-type":"item","numeric-id":2266346,"id":"Q2266346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$0C812887-1222-48EE-BB08-EF293869B179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91437bc3f5649edc6a7acb3095e2cdec844eb2e9","datavalue":{"value":{"entity-type":"item","numeric-id":3711749,"id":"Q3711749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$503DECCE-D750-4EC8-B02E-742ACF006ED2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$AD49943E-59CC-42FE-AEF6-CF09C61055D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fc27d1146b0da21fb0fbb3f5474781c089c6669","datavalue":{"value":{"entity-type":"item","numeric-id":1161742,"id":"Q1161742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$6CAA4572-507D-48F2-A41C-41A88241E614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"895886e691d85b3f1fd2f8a6af1b9616a7323e79","datavalue":{"value":{"entity-type":"item","numeric-id":3310597,"id":"Q3310597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$14BA8770-1020-4998-B250-E062132AEC39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f71c48c4615cdbfe8655b34ae58e575ac0b89217","datavalue":{"value":{"entity-type":"item","numeric-id":3328541,"id":"Q3328541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$9B01090F-8E50-4E12-94C3-B37EF635D54B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36228870059a5f0f90df014e35180ed7c6a65ec9","datavalue":{"value":{"entity-type":"item","numeric-id":1086557,"id":"Q1086557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$43CDEF07-DCBA-4E39-BA3C-9716A83BB015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03a059be13167b115275f6682f34ed2b1afe49a7","datavalue":{"value":{"entity-type":"item","numeric-id":1088659,"id":"Q1088659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$1D9DAF5B-B27B-4530-8449-BDB0B7265341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85e648ab1d102acb9b75bf5c4e0b8b52c6806d0e","datavalue":{"value":{"entity-type":"item","numeric-id":1171056,"id":"Q1171056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$6F070C2B-44E1-4BF8-8107-8D2395686987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f32e6f8496a1073deb2cc6a450426de60ad87e2","datavalue":{"value":{"entity-type":"item","numeric-id":3778751,"id":"Q3778751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$64E80C38-8361-45BA-9854-10032C1B57BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f8a45a2776e11e353b2654c9d9dc39e64443f96","datavalue":{"value":{"entity-type":"item","numeric-id":4085712,"id":"Q4085712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$12085104-26A7-47DE-8953-C7AC5506C944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2711f87013888ff581790e98f2a4db0855ba2fde","datavalue":{"value":{"entity-type":"item","numeric-id":5722348,"id":"Q5722348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$E9D98B4E-17EB-4703-B206-EFB5C8A103F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd520b49bc58e84d7c227fcb0bc974b432f91cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1166515,"id":"Q1166515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$D662FD73-27AE-4267-A378-EFEE73CE0714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a2c803a6d16dba6334f61d2fa4527d94f412466","datavalue":{"value":{"entity-type":"item","numeric-id":4132502,"id":"Q4132502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$F62FC71B-EBB9-43B4-9805-FC3CD03B5B17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67cccf664c50e16d9d7fb3a85d52ae056d65f5b9","datavalue":{"value":{"entity-type":"item","numeric-id":3260574,"id":"Q3260574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1821775$31FA8839-596E-4FDB-9504-26385ECCF62D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"edd90741b9fc250cf9d73a75c3bb87518aef8089","datavalue":{"value":"https://doi.org/10.1016/0885-064x(86)90014-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1821775$944DD65A-6473-4F15-8516-F1AFA7F789DA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f20f35514335b233442d48ec3e11313c5d219e62","datavalue":{"value":"W2018772645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1821775$3A07F30B-DAC3-4E8E-B8B3-9C29AF3E6F14","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb633435d17f24181f7a46d86efa389e94227aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3712892,"id":"Q3712892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4615fbef8414390274737d2f4cfb491c3c210339","datavalue":{"value":{"amount":"+0.8011874556541443","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":"Q1821775$770C6B5C-9884-4A1E-BF20-21DCA458D1B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a31f72a930ae019a53c5e00865aaf18754447778","datavalue":{"value":{"entity-type":"item","numeric-id":4787858,"id":"Q4787858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e3bb729439fe744c45afa5a2d73246b26e2c84c","datavalue":{"value":{"amount":"+0.799934983253479","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":"Q1821775$6DC342BD-CBA3-4024-83C6-197B8F0DDEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89e330b0061f7a44f4530d93f27dc5c22628fe21","datavalue":{"value":{"entity-type":"item","numeric-id":3978911,"id":"Q3978911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3f4758e687623f6c5ed33111c1cfeb918b3b6df","datavalue":{"value":{"amount":"+0.7994990348815918","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":"Q1821775$F1FF061F-7C7A-4E34-9C92-7BD47400B88E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a0078e0425779a9777d32f0f2b734d3f0417599","datavalue":{"value":{"entity-type":"item","numeric-id":4002474,"id":"Q4002474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53ebdba12710fe7037919399e6ae88d5c1b89bde","datavalue":{"value":{"amount":"+0.7897056937217712","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":"Q1821775$29BD764A-D604-408E-ADD1-575BD3C2F6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97832936062513acc564d653bae383074d97961e","datavalue":{"value":{"entity-type":"item","numeric-id":4730229,"id":"Q4730229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97eea68b7db007ece978443ba35a4146c287f0c4","datavalue":{"value":{"amount":"+0.7875767350196838","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":"Q1821775$601A516B-291E-4526-9AF9-9586B02AE124","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the computational complexity of best Chebyshev approximations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_computational_complexity_of_best_Chebyshev_approximations"}}}}}