{"entities":{"Q1079496":{"pageid":1090248,"ns":120,"title":"Item:Q1079496","lastrevid":69592749,"modified":"2026-04-13T08:03:54Z","type":"item","id":"Q1079496","labels":{"en":{"language":"en","value":"Quadratic functions with exponential number of local maxima"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3963573"}},"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":"Q1079496$55F3B00F-EDF7-49C2-994D-300833A7928B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"903c3605b6ffb4221ed7c4e97414e4152534693d","datavalue":{"value":{"text":"Quadratic functions with exponential number of local maxima","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1079496$1B80D78C-E1C4-4CD0-B999-89F13777ACB3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"215782daf0be570c91f27c77bf8528d2e6e8d287","datavalue":{"value":"0597.90067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079496$4F555092-9E14-4742-B107-589BB952C79A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5e3e9669ea22c4a749146c3f4708671d7d7c451a","datavalue":{"value":"10.1016/0167-6377(86)90100-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079496$E77B41EA-E448-4E0F-A731-F8A54C64FCE4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38684b7b29cf95e44150fe068164461e3ab55058","datavalue":{"value":{"entity-type":"item","numeric-id":167858,"id":"Q167858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$2ACB523C-1CAB-466A-B68B-3CC04712E3ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$EC9C915B-A98F-4EB1-ADC1-1BCBDE36FBDF","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":"Q1079496$93D0BC7D-864A-414D-8570-76E3F922DE5D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bb3bede0954e110133f9e7d35a74647f3e271f25","datavalue":{"value":"The global maximization of a quadratic function  \\[  f(x)=\\sum^{n}_{i=1}\\sum^{n}_{j=i}q_{ij}x_ ix_ j  \\]  over \\(B^ n_ 2=\\{x:\\) \\(x_ i\\in \\{0,1\\}\\) for \\(i=1,...,n\\}\\) and over \\(\\bar B^ n_ 2=\\{x:\\) \\(0\\leq x_ i\\leq 1\\) for \\(i=1,...,n\\}\\) is considered. The maximization over \\(\\bar B^ n_ 2\\) is an NP-hard problem. For f convex, the maximization over \\(\\bar B^ n_ 2\\) is equivalent to that over \\(B^ n_ 2\\). A measure of complexity of algorithms obtaining and analyzing local solutions that these problems possess is proposed. A quadratic function with an exponential \\((2^ n)\\) number of distinct local maxima is constructed. So, local algorithms for quadratic programming have an exponential worst case time complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079496$4D9F0E52-113D-481D-8653-DF4053773A32","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079496$1986FC6D-2C15-4F4B-A3CB-1C19060B7F78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079496$76D2153E-C277-422F-A1CD-C3147B318C73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079496$C43B404B-772F-4DB5-8599-84BA5889BA85","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"90bb95dbe4f2c60023e54f353984c2de8d027de0","datavalue":{"value":"3963573","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079496$AC659774-54B7-4054-B2EF-4B88CA036E97","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdfa38b08d928cbe6c142d80fc9d4b2d7f35a126","datavalue":{"value":"global maximization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079496$66249BD3-B997-46AE-ABA5-4431BB1B1FC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"166d81c703db126b55d1b910220f38f75a76468e","datavalue":{"value":"quadratic function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079496$15677C93-FCE7-47D3-94CE-0161B15C3A11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3940850096d27265a2eaeff489ff3a2d7f534c27","datavalue":{"value":"exponential worst case time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079496$1EE6D1BD-F903-4C90-8764-12B7AFFA48C0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f3ba912c6c747366fcbf58ca77660b129d8633c6","datavalue":{"value":{"entity-type":"item","numeric-id":1014034,"id":"Q1014034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$86CDB360-3BF7-4D16-B0DC-1E921FFFA9EE","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":"Q1079496$2AFAC624-A327-4C1E-8009-B9832726F93E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b64b00ffed8112f28fb0edd7383499bb3fe5b743","datavalue":{"value":"https://doi.org/10.1016/0167-6377(86)90100-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1079496$6D684FD5-B8ED-47BF-8B41-200202C7A829","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7bc380c150a33f47a247b0bd134007a28cf1a025","datavalue":{"value":"W2001988454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079496$B782604D-CCFD-41BE-9248-2E6D818327BA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$DBBDA68D-21EA-416C-988C-AA8229773846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1e239dce14973bc963cb9871e26501ddc153e9","datavalue":{"value":{"entity-type":"item","numeric-id":3693267,"id":"Q3693267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$2967B6E4-C16C-45DB-B289-B72D71BEC9EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c35c4412af23b2d48945ea93c674aa7225ae019","datavalue":{"value":{"entity-type":"item","numeric-id":3780011,"id":"Q3780011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$8CAF4FFA-8CE7-432C-B8EF-176F5CBC2D0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e371a5f10374f9c00f3dc5449f24264d858d58ea","datavalue":{"value":{"entity-type":"item","numeric-id":3686435,"id":"Q3686435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$314FCFC6-B731-4307-A875-0B1A1F298A77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66420b49775113a4962c131a254f6f2ef559bdab","datavalue":{"value":{"entity-type":"item","numeric-id":82025,"id":"Q82025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$7D9346C0-16FD-43ED-B368-61218FB60085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb1971476988dd1583d8582c2332379ed61a85fd","datavalue":{"value":{"entity-type":"item","numeric-id":4090127,"id":"Q4090127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$DFD58EED-6E68-4900-8E74-CE365A62ED66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4ba1b9629697ad5db74e47d7df6a578211989df","datavalue":{"value":{"entity-type":"item","numeric-id":5613011,"id":"Q5613011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$75267F36-B4BD-4995-8DFC-1CC12A86E3EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ab7a8ff6cfc8ed361332d7f1e300465bb27c292","datavalue":{"value":{"entity-type":"item","numeric-id":5342287,"id":"Q5342287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079496$B6FFEB50-6B56-4687-BC2E-9323B5ED8122","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9be08669684d6e36bfe5cb4df0e4fcea8cb43515","datavalue":{"value":{"entity-type":"item","numeric-id":4307716,"id":"Q4307716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09a07c62b9cb24a0981f13c355380b71ca3eec50","datavalue":{"value":{"amount":"+0.8820828","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":"Q1079496$D5C9B930-2394-4ABA-AAC7-09315DE82354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff1b3edcf9927b3b63d9fbfd462aba234d9e5a50","datavalue":{"value":{"entity-type":"item","numeric-id":810785,"id":"Q810785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67d25f69d6aa410b186bfcbef2a06847be145b87","datavalue":{"value":{"amount":"+0.8762094","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":"Q1079496$4B1D4C47-EC06-4385-9CE4-14A880B8EF99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2264b0cf0caa0b4afdab27ec63280810e983073f","datavalue":{"value":{"entity-type":"item","numeric-id":2341102,"id":"Q2341102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f541f2e3988be7942d55c90ad59af225077615cf","datavalue":{"value":{"amount":"+0.8759764","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":"Q1079496$EEEC1270-427B-49E7-8429-4507B0716F70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60d497415a4250292e360cf42e5909f2db1cc9c5","datavalue":{"value":{"entity-type":"item","numeric-id":5366909,"id":"Q5366909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73ce3612cd85c26d1ee0ddbad9be8c40ad9d2109","datavalue":{"value":{"amount":"+0.8739002","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":"Q1079496$3C6CD744-5CED-4726-B095-CC11E3F2F819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f71e331edb705493f27ba705d14007cb500d7a5","datavalue":{"value":{"entity-type":"item","numeric-id":4292213,"id":"Q4292213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faa2638f4022ccbbb6d361afcff96dfc22681e87","datavalue":{"value":{"amount":"+0.87079424","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":"Q1079496$30558D30-1A11-429D-BFA1-88EA65073273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e7d69be7b28ab25e5e6539c2461a34b880b5a71","datavalue":{"value":{"entity-type":"item","numeric-id":4295791,"id":"Q4295791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f55594f88599c5ac56aa917cd1ef890d96615fa","datavalue":{"value":{"amount":"+0.86796033","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":"Q1079496$D74671B5-6A48-4265-B4D8-FCE6A6524F0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23769205a08a03b9eedc4ac91f7a5695c6dd78ff","datavalue":{"value":{"entity-type":"item","numeric-id":5451192,"id":"Q5451192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3746ef3b9a9c0a7908beec4c822aea983558508b","datavalue":{"value":{"amount":"+0.865831","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":"Q1079496$0BF31EBD-C145-4A94-9217-DB1735A99C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b57c4c7e6e8325066f6a33fcf8f2bb6038f261c","datavalue":{"value":{"entity-type":"item","numeric-id":405955,"id":"Q405955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28871139c8eda428567508a370114eaec2b6b84d","datavalue":{"value":{"amount":"+0.86491024","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":"Q1079496$3B3819CB-4028-40C4-93A1-FA7E4F2B2AFD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Quadratic functions with exponential number of local maxima","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Quadratic_functions_with_exponential_number_of_local_maxima"}}}}}