{"entities":{"Q430828":{"pageid":432595,"ns":120,"title":"Item:Q430828","lastrevid":61777710,"modified":"2026-04-11T01:35:23Z","type":"item","id":"Q430828","labels":{"en":{"language":"en","value":"Towards strong nonapproximability results in the Lov\u00e1sz-Schrijver hierarchy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6050356"}},"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":"Q430828$C69B39B6-8FA1-48A0-88B0-0ED6BD30D05D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f87454f03b4bf3366e46a292b190c41b2b0b1a76","datavalue":{"value":{"text":"Towards strong nonapproximability results in the Lov\u00e1sz-Schrijver hierarchy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q430828$40EB1786-65C4-45E1-AA48-4B963C751EA3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3dd6e4c83d8b1f2040079211d7d94abcc4c53ce9","datavalue":{"value":"1252.68131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q430828$35C0BB2C-8B8E-489F-9B33-551A7616DA8B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dda6b61323c36da4336c78f2a00f81b412a8cdcd","datavalue":{"value":{"entity-type":"item","numeric-id":430822,"id":"Q430822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$7AFFB770-0D3C-4300-9AD2-32631390B4A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe7535c2a7fbc4354350f3fff626d063ef38fc6d","datavalue":{"value":{"entity-type":"item","numeric-id":230573,"id":"Q230573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$46B504E2-8A4C-4CC4-ADEE-4C64BD93EAE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5fa856eb9cad7c56d02923351b2c4236ede2b614","datavalue":{"value":{"entity-type":"item","numeric-id":6480589,"id":"Q6480589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$E3C16A55-D446-480A-B77E-2280657C3F2C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$98A9C924-E3E6-4B5A-A2C4-2BBDF55A2E3E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f03a3c04b271440e0460d17b6cd1c270f9267efc","datavalue":{"value":{"time":"+2012-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q430828$FA38DD61-A780-4A42-9E45-35CDD5688D59","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q430828$1CB33D21-9A61-4200-BAFA-41009634B672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q430828$5B3050BA-5FE2-4020-818C-71F60745358B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"747ca2a29edc80ef77db4b4376cee27cb80d39e3","datavalue":{"value":"90C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q430828$5C2294AC-3C7E-4F5D-8E2A-93C85EBBEFC5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d385423bf5af33357d4def3a622531a0d9f8bb20","datavalue":{"value":"6050356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q430828$13561AA1-C58E-40AF-B855-65EA78AF30F6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q430828$3468ADEF-FD4E-4E5C-927E-64FBC04E97CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q430828$12341014-D048-49CB-B826-9442000613CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"986e975208b070c5142b42b7967bb38dc4fad0f4","datavalue":{"value":"proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q430828$75314C9C-9E2F-48CB-AB94-66A7849A345D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"acc18ec7daf7cd61d454cc54d7fceefd79282033","datavalue":{"value":"lift and project methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q430828$4B5E4FE1-C65A-4E9C-845E-37F88BDFBE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ceeb500d242925ecd02f6801411fdfa0bf8566e0","datavalue":{"value":"matrix cut operators","type":"string"},"datatype":"string"},"type":"statement","id":"Q430828$42DCA0AF-8F5C-4FB1-8CF2-11E39E4941E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q430828$E9178CC4-7FED-4D41-8C56-1F3BD49D685D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e98ee8a90a9305024faf65be4543fbf88cc2f405","datavalue":{"value":"random instances of 3SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q430828$BF300670-4255-46CC-8A34-C2CF303B1470","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":"Q430828$3951DAAB-2FCC-4DC5-8EC7-4CD362628CA7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ac44dcae60a7bbcd73340f69a0b3617c6e04987a","datavalue":{"value":"https://doi.org/10.1007/s00037-011-0027-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q430828$7832D8DB-F05A-41BB-BCA9-C1181DB0827E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c6a28e03846272503a97d2ad1c931ccea61badc1","datavalue":{"value":"W2007239493","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q430828$8B22084A-DDD1-42C1-8F07-0A20E317E185","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b3ffcff20350c49ce5ec4377dc573e75c9fee18","datavalue":{"value":{"entity-type":"item","numeric-id":3002764,"id":"Q3002764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$32D37B4F-0CF1-4624-BED1-14746548577D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad6f96cf3556c62b2e9742e2f30fb947f47dc362","datavalue":{"value":{"entity-type":"item","numeric-id":5901073,"id":"Q5901073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$06A3D1BA-3403-480B-855E-A5D003A48A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a8d977f093ac551e79749f4f841b2fdb18e79ea","datavalue":{"value":{"entity-type":"item","numeric-id":3002766,"id":"Q3002766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$025A6FF6-FBA8-428A-9BA8-046CDC6FE075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1579aed2038fd9500469f94a77a8a3911f18a2b7","datavalue":{"value":{"entity-type":"item","numeric-id":5172722,"id":"Q5172722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$C438A833-2967-47B3-8602-CD14E8694897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fefa93a64939b38db387938c28d3e1c44c75632","datavalue":{"value":{"entity-type":"item","numeric-id":5317188,"id":"Q5317188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$5B490886-382C-456B-9B82-8DC78B1C051E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bafed8482918a0ff74bcc7a2a71d3b2bbb5752a","datavalue":{"value":{"entity-type":"item","numeric-id":816330,"id":"Q816330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$EF6CB09B-8BBD-49D4-9F99-5114D4E21585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$4AAC0A20-2EE4-4B39-88A2-C0FB4F84B379","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7e4ec3391671959471e0dda3a6f5f980abca5fa","datavalue":{"value":{"entity-type":"item","numeric-id":4371671,"id":"Q4371671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$3CE5A8C1-A5CF-4542-A87D-AFA92505C1B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43f4221196690a12399d25e4b0263dcb05e33b81","datavalue":{"value":{"entity-type":"item","numeric-id":4706196,"id":"Q4706196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$77040C33-A82D-4E25-9FC1-D04453F2D8DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb2302f8b1154a95a099756c11ada112026323ac","datavalue":{"value":{"entity-type":"item","numeric-id":3002778,"id":"Q3002778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$52DF08EE-EA6D-4109-A47A-E2DA644FE775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e3e1c48822d555e15270c42ee4e0fea4afe1ddc","datavalue":{"value":{"entity-type":"item","numeric-id":5704055,"id":"Q5704055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$7270FB3B-0684-4334-9B2F-BFF65E04DC82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7f992e855d8b9b42f253fc7f7d98a5e06e39cb4","datavalue":{"value":{"entity-type":"item","numeric-id":4369893,"id":"Q4369893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$E507EA88-3CFB-49B5-AA53-7F72D4BEFA30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$17871BA7-1379-4151-8AFC-287F8244B931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1a59b9106a5dd5105f2bc476300c4cdae45ec3","datavalue":{"value":{"entity-type":"item","numeric-id":3579218,"id":"Q3579218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$7577F56B-78D9-46AB-999B-557DD1413601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c94d017d89fe8a00bee910dd24c96d75202f025b","datavalue":{"value":{"entity-type":"item","numeric-id":4012419,"id":"Q4012419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$5EC3A0DC-7DAF-4C83-9FE3-87B1FCEDA3AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee15bfc318977ec4ab8712675ed372ec0dd1bae0","datavalue":{"value":{"entity-type":"item","numeric-id":5171221,"id":"Q5171221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$9AA15E82-4120-46D7-B050-BDFDCAA0E4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d5cfedfe66a3b5d774d6c8fbd31b828323bdab","datavalue":{"value":{"entity-type":"item","numeric-id":4527015,"id":"Q4527015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$E8CD3E6F-862F-4B46-869D-03C00B20A6D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09c4647bcf976edbe766a4a4b3e99ed87859ff72","datavalue":{"value":{"entity-type":"item","numeric-id":3549626,"id":"Q3549626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$DA647ADE-8E40-464C-A3C7-61F61C3C6193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b44fcaa1f05407395b26870122229a43ea361110","datavalue":{"value":{"entity-type":"item","numeric-id":3197621,"id":"Q3197621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$FEDD7F6E-3E02-47D2-A973-4E7126321A4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15d918a903cdcb12aaadc7d9d5cee11a7e58cce9","datavalue":{"value":{"entity-type":"item","numeric-id":5479373,"id":"Q5479373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$83177453-B6FE-4791-AA7D-7EACEF5D7BCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81e308d6a80bd38107e0732a6d840477ff00bb7c","datavalue":{"value":{"entity-type":"item","numeric-id":2934582,"id":"Q2934582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q430828$6007AC45-E23A-47AB-A23D-8A5541FD90DF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"111e934adb075dfe610882ac8d75ca5646e087c1","datavalue":{"value":"10.1007/S00037-011-0027-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q430828$F7523231-1C84-43A8-8221-96FA676C29F5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b70917d84ab891dc0fe8365e84f6be13225ba6e","datavalue":{"value":{"entity-type":"item","numeric-id":3581430,"id":"Q3581430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09a8b223aa0bbf337f32f02688631a519ccc054a","datavalue":{"value":{"amount":"+0.993105411529541","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":"Q430828$E5041BD0-1EA6-4362-810E-1E25A89BB2FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4accb0faa1d2fb257a56dd296495892ed6eea747","datavalue":{"value":{"entity-type":"item","numeric-id":5479373,"id":"Q5479373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d7bda9d06428d5be6b4de567a0fddbaf0d694f2","datavalue":{"value":{"amount":"+0.8456374406814575","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":"Q430828$B997F2C2-CC9B-4827-BDB8-3CA48CD03475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afc4ac075e24f22775a98f1de73679635471a973","datavalue":{"value":{"entity-type":"item","numeric-id":5390606,"id":"Q5390606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5882f123a8c64c4ff36eb81960cadbcc1ecfca15","datavalue":{"value":{"amount":"+0.8429797291755676","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":"Q430828$041B7A1C-60F3-4953-9D0D-E39DA286BB80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a5e649387572e0081d61db709bf5e37880ec1fb","datavalue":{"value":{"entity-type":"item","numeric-id":5172724,"id":"Q5172724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c419c4c9fe21050b9bdf341b1f894dbaa3746bd9","datavalue":{"value":{"amount":"+0.8028546571731567","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":"Q430828$FB534545-2286-4919-9CBE-BEF7AC9BBF7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1896c7bf5874b1f9908cc8e93cff6b7bf5d5c3b","datavalue":{"value":{"entity-type":"item","numeric-id":3177811,"id":"Q3177811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd7f451a1ebc556e58670130640d5ffb1409a0db","datavalue":{"value":{"amount":"+0.8009490966796875","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":"Q430828$BDCE5225-5182-45AF-8FE1-24D2817005F6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Towards strong nonapproximability results in the Lov\u00e1sz-Schrijver hierarchy","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Towards_strong_nonapproximability_results_in_the_Lov%C3%A1sz-Schrijver_hierarchy"}}}}}