{"entities":{"Q688442":{"pageid":690291,"ns":120,"title":"Item:Q688442","lastrevid":63494184,"modified":"2026-04-11T13:32:59Z","type":"item","id":"Q688442","labels":{"en":{"language":"en","value":"A well-characterized approximation problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 444831"}},"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":"Q688442$1521BE60-137B-4C3E-A0FF-DB67B46EEF08","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d2fca1550ead3711ad0f2af76f4ea2ac1c02e2e","datavalue":{"value":{"text":"A well-characterized approximation problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688442$DD7D91A3-C9D8-4D76-A22C-7622ADDBC536","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"860960c1b37474c2689d60f10525ba1a0720cdbc","datavalue":{"value":"0782.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688442$CCA8D853-6788-4DB2-9A18-07E6712CC7B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3573ae2d5ff499e1ba1420629d1418cf011c5b7c","datavalue":{"value":"10.1016/0020-0190(93)90076-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688442$9971F860-5B9A-4C1C-A872-33C4B9DEEAB1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d14ec0d2c25271c51dc324d4a7cd01ba1a383ba","datavalue":{"value":{"entity-type":"item","numeric-id":178481,"id":"Q178481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$960F13C2-AC2E-4EA0-AF53-48ED7C23C09A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9023554ef09c8d4f4813676b620b15e4c22a0cf","datavalue":{"value":{"entity-type":"item","numeric-id":1083474,"id":"Q1083474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$CE0168F7-C2D3-4AE3-AEA7-1A00E24D264F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9db261fcc879c228fbea99e04932baa70258293","datavalue":{"value":{"entity-type":"item","numeric-id":1202921,"id":"Q1202921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$A31C2750-DEAE-43F9-8396-2D6B3296A649","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$92C3384B-D009-44A3-963F-48E200F77073","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f67bd20fe430f6951bd39751d5694c2262cae6a7","datavalue":{"value":{"time":"+1994-03-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688442$E4E11862-CB26-4991-A3CF-662C10ACCB05","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8bc0724161e2710f07215b0aaaf43aac43e9ab33","datavalue":{"value":"We consider the following NP optimization problem: Given a set of polynomials \\(P_ i(x)\\), \\(i=1,\\ldots,s\\), of degree at most 2 over \\(GF[p]\\) in \\(n\\) variables, find a root common to as many as possible of the polynomials \\(P_ i(x)\\). We prove that in the case in which the polynomials do not contain any squares as monomials, it is always possible to approximate this problem within a factor of \\(p^ 2/(p-1)\\) in polynomial time for fixed \\(p\\). This follows from the stronger statement that one can, in polynomial time, find an assignment that satisfies at least \\((p-1)/p^ 2\\) of the nontrivial equations.   More interestingly, we prove that approximating the maximal number of polynomials with a common root to within a factor of \\(p-\\varepsilon\\) is NP-hard. This implies that the ratio between the performance of the approximation algorithm and the impossibility result is essentially \\(p/(p-1)\\), which can be made arbitrarily close to 1 by choosing \\(p\\) large.   We also prove that for any constant \\(\\delta<1\\), it is NP-hard to approximate the solution of quadratic equations over the rational numbers, or over the reals, within \\(n^ \\delta\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q688442$5ECCB3E2-C32F-40CE-B78C-59B5B964735E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688442$C475F02D-EFB8-42A9-8C3D-44B60B07B5EE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"74e54fd95c663a73cd2e3372acdf4d104d59effc","datavalue":{"value":"444831","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688442$9DCCCCA6-8725-4796-BABC-1B365E7FD26F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q688442$62C9F332-FAAF-45AA-BD00-62009FED17F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q688442$6F0349F7-E76C-4C9B-BF0B-A08E019CBA02","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6164bd08c01e558b0182b9545ddccff8a19eafdb","datavalue":{"value":"Q56959141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688442$D2F31576-0CB2-4226-A07B-36C4B44DE487","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"940b0d75116b08296727c411debf20954926b103","datavalue":{"value":{"entity-type":"item","numeric-id":1083474,"id":"Q1083474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$FC69B552-0356-4259-8F5C-B2A87A172F2A","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":"Q688442$E920A672-EC52-4485-B236-6DA5A0DFD2CF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09a3c4a236e1a86a9306468a70629484f76019f1","datavalue":{"value":{"entity-type":"item","numeric-id":4014640,"id":"Q4014640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$649EBE1E-6FCC-46E5-9FCD-3B9895F7E551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7258962f550bf808b8ce0edfe0f9b2099a09d076","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$596AAFE2-B6E9-43F9-A940-E8E5748DBEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46904ca7712e5807737130ff54d9af7fbcef5eda","datavalue":{"value":{"entity-type":"item","numeric-id":4230321,"id":"Q4230321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$816AA8AD-8A9F-4904-9A72-1774973D8397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"127ecfb8af7bef406c624e706903bb6e0473005e","datavalue":{"value":{"entity-type":"item","numeric-id":5248498,"id":"Q5248498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$50861495-A042-4CC5-A072-047C7E463FFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c766e6fd8d508654144780e9094a8eb3c0fc3851","datavalue":{"value":{"entity-type":"item","numeric-id":2743964,"id":"Q2743964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$4588386B-B8F4-47F2-817B-5F3E58EEE5A2","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":"Q688442$394533B7-ACAB-4404-9299-B67044F1C92D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d8549af636d2abe2c2be6c22ae2647ebb36e4d3","datavalue":{"value":{"entity-type":"item","numeric-id":5248497,"id":"Q5248497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688442$A4E22843-5D1B-4B6E-A9F6-8CE7A5DAB5BC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"56dbbb78fde2cfc792228aa1b99ba6e6de3bcef5","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90076-l","type":"string"},"datatype":"url"},"type":"statement","id":"Q688442$0CA1F7C5-3308-4C56-9CDB-B4D535D80D63","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f04143b8098631f76aca068c9694631b6c7bc93e","datavalue":{"value":"W2117913620","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688442$1C7DD439-2556-47E0-A79D-63D9EA183A01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f304fa03d15257d1a1ec7ab77cea13a503618fb3","datavalue":{"value":{"entity-type":"item","numeric-id":3088098,"id":"Q3088098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58564696de18852b2ef35adb66d63dcb7e28c60e","datavalue":{"value":{"amount":"+0.8027376532554626","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":"Q688442$2B6D0519-7D9B-4AE2-9B2C-D992F6448E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82cf499c17bf6956724d141d929f304255fbab7a","datavalue":{"value":{"entity-type":"item","numeric-id":1906280,"id":"Q1906280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"445a5df70ce7531cbef3edb8bbeb63b3903080f9","datavalue":{"value":{"amount":"+0.8013945817947388","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":"Q688442$897E0DE1-B62D-488C-863E-5EB6C1B4C37E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e4cf95faacc64212b6cd6fbc37900d89e780031","datavalue":{"value":{"entity-type":"item","numeric-id":5419111,"id":"Q5419111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"445a5df70ce7531cbef3edb8bbeb63b3903080f9","datavalue":{"value":{"amount":"+0.8013945817947388","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":"Q688442$D5F7E4CA-EF5C-4723-9414-6EF296C8E066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1b65112490151e1e3e734b769178083d8b70adf","datavalue":{"value":{"entity-type":"item","numeric-id":1045886,"id":"Q1045886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d566b63f58ad8f7b337305e4cc79d35abe9e46d","datavalue":{"value":{"amount":"+0.8012183904647827","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":"Q688442$7D004459-E7B2-491A-BEC2-B3527EB240C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"051f6ffa9130bde4503ab2fa0dc57c452af8cc94","datavalue":{"value":{"entity-type":"item","numeric-id":3191597,"id":"Q3191597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1db943df38e5e9af17106d40075386a3fb0eca40","datavalue":{"value":{"amount":"+0.7963482737541199","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":"Q688442$1AD660A5-B9EA-4B9E-B8A8-136811A08077","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A well-characterized approximation problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_well-characterized_approximation_problem"}}}}}