{"entities":{"Q1853564":{"pageid":1864306,"ns":120,"title":"Item:Q1853564","lastrevid":74322270,"modified":"2026-04-14T19:31:50Z","type":"item","id":"Q1853564","labels":{"en":{"language":"en","value":"MAX3SAT is exponentially hard to approximate if NP has positive dimension."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1857094"}},"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":"Q1853564$2691BC12-43D7-47B5-A72C-2A6CD77CA3E1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4572bad5da297a053cd6cf1ba320168ddd881a60","datavalue":{"value":{"text":"MAX3SAT is exponentially hard to approximate if NP has positive dimension.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853564$9519CB4E-B44D-42E8-8D42-E21432F0E05E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4511a80422cb898b6982320786fae215588f5f2e","datavalue":{"value":"1061.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853564$663FB6BB-C92A-429A-B05D-8CA58C0C74BE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"db795c3545bbb9cc718705729f618e4a13f198ba","datavalue":{"value":"10.1016/S0304-3975(01)00340-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853564$5CD910FC-FDEC-4286-84D1-6D942996AF4B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ee1f3cf09e866f3eab6561711e5db4300ad48b0","datavalue":{"value":{"entity-type":"item","numeric-id":596116,"id":"Q596116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$E4EBDD05-CF8C-4212-A49A-7B03504CA46F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$B5FC25F1-4DFC-49C7-8A10-984864D0551F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853564$C2FDE726-A786-4A6A-93DB-823E5BADEB32","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853564$534D29A0-1007-485B-9570-51B188EABB07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853564$A2F8F49B-418B-4771-8F04-563D4DAC70AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853564$BE4BD392-DFA6-47B5-AF0E-4D7161C79985","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5c5450ccaba3fdcc1557b16c79c0648514384384","datavalue":{"value":"1857094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853564$BE926672-1A84-4016-B029-E04CA2D91324","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9318f68a45dcaad331b6e07f068083eca872d393","datavalue":{"value":"Resource-bounded measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853564$7F14BD73-3ED1-4D5C-9304-26CCF6C65FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cc9c3e4edac982f309fd2de6b740f01e42a132c","datavalue":{"value":"Resource-bounded dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853564$66C48DAC-DB9A-4DDD-9B4E-BB297727AAA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1346aa64d89c3b70923bab460d0677e75f9c236c","datavalue":{"value":"Inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853564$E743591D-011E-48E1-9184-5C5B30BF4A67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80a9e6b91aea4bf072e162e5d81414212c57fac6","datavalue":{"value":"MAX3SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853564$5BAC25CF-6784-43D7-80AB-B6C29B2159DC","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":"Q1853564$00495794-0120-4E6A-9B63-96E0B39DE018","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$CA56ECDA-CFB1-47DC-84AF-87448B61FEEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9eb8cad10997fb52aeab3415a2efc3b2dd6c760","datavalue":{"value":{"entity-type":"item","numeric-id":5957907,"id":"Q5957907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$CB2F74BF-D528-491B-9881-2D074E83A274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dc34d0d5c037382989dfdf547b1eabd2cc7fe04","datavalue":{"value":{"entity-type":"item","numeric-id":4263713,"id":"Q4263713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$7A2DD71A-A0AF-45DA-B9D0-756E53081203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4f6417af3313b2a4f1959b9dee0bb7940ea475","datavalue":{"value":{"entity-type":"item","numeric-id":4526964,"id":"Q4526964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$B9F8E5B7-9F2F-44A8-BAFD-0881FCBCE553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d38b4a76df166b15ffd8426406cd56803e157294","datavalue":{"value":{"entity-type":"item","numeric-id":1190985,"id":"Q1190985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$EA7568DE-709D-4AC0-9718-44F96715401D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c9985f6f87a12e675c0a4ce5a1c70bbd22a418a","datavalue":{"value":{"entity-type":"item","numeric-id":4266481,"id":"Q4266481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$34585D80-1E5F-4779-B2EC-11F29E617FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f235ba32c2312416178e80711d9affd8fc874d","datavalue":{"value":{"entity-type":"item","numeric-id":4305356,"id":"Q4305356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853564$F0A8626A-BCEB-43BD-AF81-E9F485CF202E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8ca329ba49bd914b2e887caf341ccd852c7040f","datavalue":{"value":{"entity-type":"item","numeric-id":5957907,"id":"Q5957907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e8b63fd627d07201d322fd4f82f739848272206","datavalue":{"value":{"amount":"+0.800353467464447","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":"Q1853564$E3A3A97B-EA8B-4893-908D-58A8FC1FD7BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66a30ac10cd326287ac3209c357ff1436b5eaa64","datavalue":{"value":{"entity-type":"item","numeric-id":5696308,"id":"Q5696308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b59d6cad51256062bf889e06ad976eebadf998d4","datavalue":{"value":{"amount":"+0.7949951887130737","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":"Q1853564$83489059-CCB5-4785-BEA9-110A89DAAEF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40345cf09666205ac7b84e3a219b20757a155c07","datavalue":{"value":{"entity-type":"item","numeric-id":6487958,"id":"Q6487958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21cf52240daf4a5a6f108c40dcf4fd7d4ed71202","datavalue":{"value":{"amount":"+0.7835074067115784","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":"Q1853564$AA71A761-A8BB-4941-8A4C-4A5153D301BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c15d820d2802a6d56d2a102938e4ed4dd8b1d64a","datavalue":{"value":{"entity-type":"item","numeric-id":4250183,"id":"Q4250183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b23ad4501f71f4f4cbded795c684f697e82af295","datavalue":{"value":{"amount":"+0.7763646245002747","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":"Q1853564$1EA108C0-5D72-4A2D-9519-33CEE18A95F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f154465087b074874b8b3ba81ee1aa3deab47c1","datavalue":{"value":{"entity-type":"item","numeric-id":5691296,"id":"Q5691296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b23ad4501f71f4f4cbded795c684f697e82af295","datavalue":{"value":{"amount":"+0.7763646245002747","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":"Q1853564$F2EEFF4F-746F-4B4F-9DC4-26859104CB1D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"MAX3SAT is exponentially hard to approximate if NP has positive dimension.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/MAX3SAT_is_exponentially_hard_to_approximate_if_NP_has_positive_dimension."}}}}}