{"entities":{"Q2913811":{"pageid":2924531,"ns":120,"title":"Item:Q2913811","lastrevid":57523749,"modified":"2026-03-31T06:38:13Z","type":"item","id":"Q2913811","labels":{"en":{"language":"en","value":"Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6087403"}},"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":"Q2913811$096B9E73-7F1D-4068-8C4C-811982A8D351","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47b01ea7cb7cb54c4ae2db9a5a21807364564dc7","datavalue":{"value":"1255.68303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2913811$6F86CC9D-BE14-497A-AF54-4BD46832E936","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c036cc59d8136b1c1d330e12aacdea4899ce840","datavalue":{"value":{"entity-type":"item","numeric-id":293456,"id":"Q293456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2913811$F10BC56E-3743-408B-BF99-B6B7CF77B2BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f72af91a7dbb11990d9fcd0f2ba0c2b90a5c150b","datavalue":{"value":{"entity-type":"item","numeric-id":6040539,"id":"Q6040539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2913811$5434860D-E706-49A3-96FD-DA6FFB3991DE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"11632bef515b8b0af0e8d65098d262d28b5f8c42","datavalue":{"value":{"entity-type":"item","numeric-id":2816408,"id":"Q2816408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2913811$6D79D839-BF6A-45EF-9A2F-2153F93A6D2A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3fc6cf2e793ffe0cfa0f8a10182fc08299b3419d","datavalue":{"value":{"time":"+2012-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2913811$616A1775-C477-4E81-B11B-AB8F0364F360","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2913811$9A85C5F8-F820-464A-B051-8BFC4CA85C44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2913811$585802CA-1A12-4442-9460-B69A0FA866CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2913811$B5D0ABFE-7E5A-4BE8-AC13-90B2CE47486A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"27bbc5345f0d7f0694c343f1a445e80061c3ac33","datavalue":{"value":"6087403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2913811$941799AC-D14B-45AE-82B1-3465C27025A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2913811$FB7E9717-3C0F-4D2C-9775-9909504C48CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2913811$228AFA68-B4C1-4AE6-9883-84B5369942F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e088df1fc83158b6e99a19b8d624735c4cb0c49e","datavalue":{"value":"unique games conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2913811$55857DB6-B217-4D79-A8C0-63BA75F7B9F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b71b8d98421f6ed3c16bba18b9a925fd088395b2","datavalue":{"value":"Horn-SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q2913811$BD5E9E93-C171-4B6E-90E7-2B362391DEF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef3359963103ce91301df426220214c1629f9c44","datavalue":{"value":"exact hitting set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2913811$63EBC855-E8B3-44A4-8C15-D3EF04D21E73","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":"Q2913811$223E2F28-C2EF-418E-A513-C3A14E86A3D5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"acfaa907be6c1988285217c8931714121ba6327e","datavalue":{"value":"https://doi.org/10.4086/toc.2012.v008a011","type":"string"},"datatype":"url"},"type":"statement","id":"Q2913811$83D4EA99-8B29-426D-9C4C-A781B01CDAE2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e9d63d72979daa21de558dd24cbc805ac7446916","datavalue":{"value":"W2611404581","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2913811$A8CE04D2-A517-48D1-A70C-406A6AAF8AFA","rank":"normal"}],"P223":[{"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":"Q2913811$F55C1DB6-0571-4929-92B2-69EC7EB5114A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a276206f83a38242ab9d04803311e19708c8fac","datavalue":{"value":"10.4086/TOC.2012.V008A011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2913811$3AC25BD4-A231-4FD7-A6ED-31357F4F54AE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8902f3a93117f7eb565873e0c2d5f10c7ff96d40","datavalue":{"value":{"text":"Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2913811$438CB633-E74F-4EF8-9050-798E3AB4601C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"171ab77dec29e847f7d8fda73a4fec90be0fef66","datavalue":{"value":{"entity-type":"item","numeric-id":5365140,"id":"Q5365140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ec8281d8472c513b7abf2259476a570053576eb","datavalue":{"value":{"amount":"+0.9976701140403748","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":"Q2913811$9C3FAE0E-A72B-4BAB-BDB0-60E83E523E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32dd2e8e1d45c784600471dd110c6a7c63b5a39c","datavalue":{"value":{"entity-type":"item","numeric-id":4542575,"id":"Q4542575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5307248a436ef7a938f4a5b90f0fa4e09ff02b8","datavalue":{"value":{"amount":"+0.8322874307632446","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":"Q2913811$485EF5B1-9AF1-4A93-B20E-C5C652F0A8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75f6a7e82e70ee0d2ea710d4320ab27c04771144","datavalue":{"value":{"entity-type":"item","numeric-id":4636446,"id":"Q4636446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5307248a436ef7a938f4a5b90f0fa4e09ff02b8","datavalue":{"value":{"amount":"+0.8322874307632446","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":"Q2913811$E0E05DCA-CF76-447C-88FA-ACE446468B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7cbfc30883463b8f33020d98e1474c9385c9219","datavalue":{"value":{"entity-type":"item","numeric-id":2706139,"id":"Q2706139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b73237f7a448e3d57f06e9e86cf1411cb648836e","datavalue":{"value":{"amount":"+0.8117808103561401","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":"Q2913811$83240F7C-4CB0-4A99-A86A-F841FFA17539","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":"b73237f7a448e3d57f06e9e86cf1411cb648836e","datavalue":{"value":{"amount":"+0.8117808103561401","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":"Q2913811$BC825441-7D20-4DFA-9FC4-BC54AC58ECB7","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2913811$5D97E909-84B9-418C-A6A2-57E258B2D068","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2913811","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2913811"}}}}}