{"entities":{"Q685495":{"pageid":687344,"ns":120,"title":"Item:Q685495","lastrevid":78189317,"modified":"2026-05-06T11:00:01Z","type":"item","id":"Q685495","labels":{"en":{"language":"en","value":"A note on the descriptive complexity of maximization problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417403"}},"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":"Q685495$108352F5-2C7D-474B-BB87-BC0106E12B89","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d7ee2b68cccdd064055ee418de65dbe93029a108","datavalue":{"value":{"text":"A note on the descriptive complexity of maximization problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685495$8C7007EA-203D-43E8-B8D4-D8C67094C304","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"97b8e6e8882440266ccd280ee6d35e24da9705ef","datavalue":{"value":"0778.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685495$89E45BA7-EB81-4518-B699-05E2E451ACC7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"093695c4d01237297f0c69893dbc6c27e3e9d083","datavalue":{"value":"10.1016/0020-0190(93)90151-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685495$94445BB8-CE8C-4243-A666-2FC1179C7EB8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"91d50cdeb23e4905b247ff213c2d9fe1cf6c555a","datavalue":{"value":{"entity-type":"item","numeric-id":222483,"id":"Q222483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685495$57FCCF51-DB86-4BA3-BD3E-421FE1FC69FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58acf3741ec940036229b64a01b0d77bd499cb0a","datavalue":{"value":{"entity-type":"item","numeric-id":590536,"id":"Q590536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685495$58A84FF7-35F5-422F-92CB-88A6926F568E","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":"Q685495$BF881961-5B8F-434B-BFE0-AE6D212872FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a626d589150434ddedb6dea454b02c574516fd1d","datavalue":{"value":{"time":"+1994-01-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":"Q685495$CFAA50EE-8E9E-49E1-9721-5127B3DB9EEE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"84e39055024fa26183a579e8ec979750b8d27784","datavalue":{"value":"\\textit{A. Panconesi} and \\textit{D. Ranjan}, Quantifiers and approximation, in: Proc. 22 nd ACM STOC, 446-456 (1990)] have introduced, two classes called MAXII and RMAX(2). From the definition of such classes, it follows that the latter class is a subset of the former. On the other hand, \\textit{P. G. Kolaitis} and \\textit{M. N. Thakur} [Logical definability of NP optimization problems, Tech. Rept. UCSC-CRL-90-48, Computer and Information Sciences, University of California, Santa Cruz (1990); Approximation properties of NP minimization classes, in: Proc. 6th IEEE Structure in Complexity Theory Conf., 353-366 (1991) have proved some surprising relationships between classes of optimization problems whose optimum is definable using existential or universal first-order formulae. In particular, they have also proved that \\(MAXNP\\subset MAXII\\).   We improve that above inclusion by showing that \\(MAXNP\\subset RMAX(2)\\). This is the best we can obtain in terms of \\(RMAX(k)\\) classes, in the sense that \\(MAXNP\\not\\subset RMAX(1)\\) unless \\(P=NP\\). Furthermore, a corollary of our result is the \\(MAXNP\\)-hardness of the MAX CLIQUE problem which has already been proved in [\\textit{P. Crescenzi}, \\textit{C. Fiorini} and \\textit{R. Silvestri}, A note on the approximation of the MAX CLIQUE problem, Inform. Process. Lett 40, 1-5 (1991; Zbl 0751.68027)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q685495$35C0FE49-7557-4A11-ABF1-006082AAAE3B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685495$9C916A7C-8B33-45F1-B19E-2BB810EBD9B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685495$450D6082-BF93-4A0F-AE99-066735DE8F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685495$ACE0AA0E-006C-40DB-B12A-7A0DDAFF19C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5384be77e0087eda551138ed8068fab937f80fd9","datavalue":{"value":"417403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685495$9C21869B-58FC-4F30-B614-F432A012DA64","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"420132b0a86bb9bedd0eeeab0b7b74055a6e96fb","datavalue":{"value":"descriptive complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q685495$8C2A23A2-CD72-4E72-94C5-998B860E5F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a59b1493a3dfce77efe9c02f17396ec193aeaaf0","datavalue":{"value":"optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q685495$A1D7F174-B703-42FD-A2D3-BF9CC707F3F8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"01b0989d65d3fe37f1a608a8cd96e416bda56c38","datavalue":{"value":{"entity-type":"item","numeric-id":200913,"id":"Q200913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685495$813FA7B9-3E94-4465-9C1B-6AA31A2D3BBB","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":"Q685495$D8CC9B82-E0DC-4AD3-83D9-0275640FA28C","rank":"normal"}],"P223":[{"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":"Q685495$35018BE0-CF1E-4EBF-A91E-8B5150E980E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bcfa4e47d5c552eaf96f3ca63d740f4608ec53d","datavalue":{"value":{"entity-type":"item","numeric-id":1183423,"id":"Q1183423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685495$F6D273DD-EB8A-4F78-B484-04161F07F518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685495$42FDB405-6D49-4F37-8CB1-86E4E0F49F92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685495$517E4306-69D8-49AC-936D-D8E02B5F9F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d80e7a1380ec025afaec5721f2a48c29a99d902d","datavalue":{"value":{"entity-type":"item","numeric-id":1342522,"id":"Q1342522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685495$32218EDD-D208-42C7-A6D4-CC563F3B0096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685495$8A4401AC-CD61-43D7-8E81-4DC20E8584C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2248dd41129637bf919fb3d1ac09690399c1e3de","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90151-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q685495$723FDD39-646A-4211-8904-3CBAA99B9D72","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ea044e338ea4c2fb4f22db270ee05a852923f78a","datavalue":{"value":"W2052673159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685495$FF716DD2-4D31-4838-8222-2A916593C391","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cf9ef08ac42c248cfc3b3eafc849961fc6de0d3","datavalue":{"value":{"entity-type":"item","numeric-id":5947116,"id":"Q5947116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28b36e4a93c1b4a90cee7cbb0bf4f18d732a0714","datavalue":{"value":{"amount":"+0.72234505","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$289D72F4-BB93-4501-90FE-202A87EAA5FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5daa2b089a3493f4892f87faf65974516acae6b","datavalue":{"value":{"entity-type":"item","numeric-id":4253663,"id":"Q4253663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35d9461b9d21e32148412d0d4dd64c93b306e11a","datavalue":{"value":{"amount":"+0.7080301","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$65878BEF-4DA3-4759-A240-288BA5D86324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23a02fa644142d9b6b129ad111734b0675336703","datavalue":{"value":{"entity-type":"item","numeric-id":1197604,"id":"Q1197604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49abdcedee704db29fd485e8e636ed1e48fa3a44","datavalue":{"value":{"amount":"+0.7071899","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$28175C19-CBD7-4EDA-A2F2-28FC4971E7BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"659a6d2c61de42e1264c1e3bad781721575238ad","datavalue":{"value":{"entity-type":"item","numeric-id":3143144,"id":"Q3143144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89ca70167f1a96f1da6978544d5e69ce8116bef6","datavalue":{"value":{"amount":"+0.7048921","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$BF916322-74A4-4AAF-BDF8-E54A013BAE6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0f86f31a1575ccaca60ac304aee064efe72e344","datavalue":{"value":{"entity-type":"item","numeric-id":4724603,"id":"Q4724603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e72eff8606c10919ca0cfeef4a328d8591658252","datavalue":{"value":{"amount":"+0.70353234","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$068BCA5F-F267-4D66-9204-A17C42E59152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3f1f6a33d592092c3a3a70af5d65464188b72fe","datavalue":{"value":{"entity-type":"item","numeric-id":1797435,"id":"Q1797435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b3225464e614c926bc867ffab29d3cf10b688cc","datavalue":{"value":{"amount":"+0.69990516","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$CFD25CE2-1B92-42DF-893F-E650709CB15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7471d7ab12f9c9045213cbaa1c9ecede6367af17","datavalue":{"value":{"entity-type":"item","numeric-id":5245182,"id":"Q5245182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edbfa148b2dd2d9844be9dadbf73b7b202b44baa","datavalue":{"value":{"amount":"+0.6998427","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$E3B167AC-D2DD-4419-A93D-9B735CF1D88B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc1a177311998be2ee80493553122e625018020f","datavalue":{"value":{"entity-type":"item","numeric-id":1644912,"id":"Q1644912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f9af50e5180651c157180cc7f819c145938bec5","datavalue":{"value":{"amount":"+0.6981413","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$8AA9537A-D7BF-4B9C-A5DE-96616A95661B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"176bfd10f1e656ab516bd6855ff336e55b5c7217","datavalue":{"value":{"entity-type":"item","numeric-id":3783525,"id":"Q3783525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bd65627c48e7cfc9565cc6dd381c03f957146f4","datavalue":{"value":{"amount":"+0.6948377","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$9B9B455A-E767-4D7E-90B1-92B613B57F73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c70e6da7712185c3c3aa99f7f765edc77c96f74","datavalue":{"value":{"entity-type":"item","numeric-id":5900434,"id":"Q5900434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"254ff6c992d945a36a43aaf5c0b51e280fdfebac","datavalue":{"value":{"amount":"+0.69389886","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685495$C012C4D7-656A-4A55-8987-8CE757527FDD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the descriptive complexity of maximization problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_descriptive_complexity_of_maximization_problems"}}}}}