{"entities":{"Q2732273":{"pageid":2743012,"ns":120,"title":"Item:Q2732273","lastrevid":41943665,"modified":"2025-05-19T08:49:10Z","type":"item","id":"Q2732273","labels":{"en":{"language":"en","value":"Minimum propositional proof length is NP-hard to linearly approximate"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1623516"}},"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":"Q2732273$71FE29CF-DA26-4C63-AA73-BC3AB576B3E1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"faa3203565c0a12292fdd73820b230d4fce3084a","datavalue":{"value":{"text":"Minimum propositional proof length is NP-hard to linearly approximate","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2732273$523688B2-4886-415F-B8A2-8E5BD6DE3C76","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"72617b4aa7bc1dc3f5d5f5789ede2c64b3a515ea","datavalue":{"value":"0977.03032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2732273$17B9004D-380B-487C-90F1-D9D4D6BF3AFF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e08c05a3d4d9235b8679d0b25a73a910de9b0976","datavalue":{"value":"10.2307/2694916","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2732273$6908E2C2-C992-4D87-B695-28AFCFB4D1B1","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":"Q2732273$C79E3FE4-CF89-43C4-A568-F13FEA273E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3bd4342967813d6c73138a0b6a4a791b0a8c6593","datavalue":{"value":{"entity-type":"item","numeric-id":287984,"id":"Q287984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$0DC3024C-25A6-4E99-A463-91867915CAA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"38b40ed6cb099fba5da493703b11839c0af89042","datavalue":{"value":{"entity-type":"item","numeric-id":202089,"id":"Q202089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$A7982CCB-ABD6-42C1-BB55-339B2DCCDE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"556b5f897f5d545f04c26b56d4624f5cc4b2661a","datavalue":{"value":{"entity-type":"item","numeric-id":195654,"id":"Q195654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$052D3581-0A2A-4402-AF1A-4706C27E2823","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"da1e102b79cffd268b6f68feaae2005a6fba4d8e","datavalue":{"value":{"time":"+2002-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":"Q2732273$19EA4CB7-2F8F-43C1-9A84-2445CACBE3D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2732273$9F48BAD4-9AC0-4ED8-95CB-2866CEF960CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2732273$76D2CC2B-EF58-4B7F-91FE-D49630EBFDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2732273$83A2CF4C-17C1-4146-8229-4A648D418704","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"49b3d96ae2022aafd315e9d7d267d9c84d7f86f0","datavalue":{"value":"1623516","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2732273$D049106C-6D1D-45DB-A89A-63880EB01577","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2732273$5EB5FC33-B997-4064-B4D6-429BD590FFEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8d344a99661ee06d13927343925f394f93e05fe","datavalue":{"value":"resolution refutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2732273$4E37D443-A020-435D-A548-F7484CFE9A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"479bfcba5e8f28e24e635c6ad0a6d23ad915d6f1","datavalue":{"value":"minimum propositional proof length","type":"string"},"datatype":"string"},"type":"statement","id":"Q2732273$CAF0DC4A-8F4A-4611-9000-7E1EDF94F17F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42f7e939acf4ed91cdd39f1bd56576107c47fb06","datavalue":{"value":"Frege systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2732273$D584E8B6-1526-442A-BD4C-E0B15FF7B22B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfac5eb6431ec88e2a6e9bafbfcf7b49dda794fc","datavalue":{"value":"resolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q2732273$2D1C287C-5A15-47D4-A17D-8073A0E65BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211f3c345d1c27387d231726f7e79d65298863cc","datavalue":{"value":"polynomial calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q2732273$C3294E38-5CBA-45EF-92FE-AD945342703A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c7d4aa0d3cf1745112ae7d594a2a5578f4e767f","datavalue":{"value":"sequent calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q2732273$078DDD2A-3005-4A59-A0A3-3EDE27DD18FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2732273$0C02EEE3-C8C1-41DA-AB91-1BC21B726BEC","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":"Q2732273$355DAD68-3B96-4883-B3DE-063BF56FC1E6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0b19e1caaf78e5582d55b8f41120c0d166ae0c5f","datavalue":{"value":"https://doi.org/10.2307/2694916","type":"string"},"datatype":"url"},"type":"statement","id":"Q2732273$376D32F1-98E6-4320-B885-59C74E695AA3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c8c563eb2a07ec330792d7c8ecae0149e47722cf","datavalue":{"value":"W2006906201","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2732273$63AD38E6-293B-47C9-BDF1-BB992C1EE043","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e956899ee0a7e06c94f20261b5948e49f9acb5d8","datavalue":{"value":{"entity-type":"item","numeric-id":4323730,"id":"Q4323730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$A0A9386D-52D0-47F7-BCF4-C0FE4648E262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85859d4bf1a3e88a94a43f3e1ce8b0cfd1f2c77b","datavalue":{"value":{"entity-type":"item","numeric-id":3002852,"id":"Q3002852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$F9876D7B-1D63-409F-B49D-7E73EAA26F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"702f0afed0ff12acec467dc949a7a6178a30a71a","datavalue":{"value":{"entity-type":"item","numeric-id":1356888,"id":"Q1356888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$26F361F7-27EF-4B21-8A07-B123E3F011B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bea75da9fa67a5f77faa9362cd4aa6c737c792a","datavalue":{"value":{"entity-type":"item","numeric-id":4194955,"id":"Q4194955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$9137A168-4D70-4710-9CB5-9E5C2AD6FB60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58f4844883d38ba5b8da2bd118d050bc2a66329c","datavalue":{"value":{"entity-type":"item","numeric-id":1908815,"id":"Q1908815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$4F98FD2B-E5D2-4A8D-AE45-8BBC2168C704","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9ca9f29a18283b75d2a8708f9db9118fdc42729","datavalue":{"value":{"entity-type":"item","numeric-id":4218098,"id":"Q4218098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bba8dcad5534974698b55f5eb6326566f6b55d4c","datavalue":{"value":{"amount":"+0.9877911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$CB95406A-464B-44A6-A3AC-F62431912915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fafb7c40fe2204784faeae2bce3ee6d639c51d6f","datavalue":{"value":{"entity-type":"item","numeric-id":5713719,"id":"Q5713719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a57b791ade7b3202e164df282fadd5fcbbf0ee16","datavalue":{"value":{"amount":"+0.8687665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$F34171C7-F90E-45A9-B0B8-8BD5494A031C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"045e1726bef472b5048e086c8f8115678a1b9781","datavalue":{"value":{"entity-type":"item","numeric-id":4292593,"id":"Q4292593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8678f784280efc93290156761b2f8a221c1aa53e","datavalue":{"value":{"amount":"+0.8686994","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$3146892D-355A-4FA4-81F5-E1F434A86806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccd98b6448df6858b18879d10f561463d4ffb731","datavalue":{"value":{"entity-type":"item","numeric-id":1874241,"id":"Q1874241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"789c33b1590a1431de8cf1f2ea98e1d5653e14c8","datavalue":{"value":{"amount":"+0.86724627","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$F47B92CC-ABAE-491E-A6FB-7F64DC557198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b99d328c6ac60d1ab7cd9f45b93591d3c3505f00","datavalue":{"value":{"entity-type":"item","numeric-id":1908815,"id":"Q1908815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bb1e5f95484c5812d8f6cfe5b0a5057f4a4f735","datavalue":{"value":{"amount":"+0.86682165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$A6AB5E96-147D-42CE-9A5A-1119062F161B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bccd342851f82092c36d356a3c8af859406901c2","datavalue":{"value":{"entity-type":"item","numeric-id":1374208,"id":"Q1374208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bcdfaa3f037dc95f6fb3e7afc1ed1acc13cdff4","datavalue":{"value":{"amount":"+0.8603777","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$EB2D5827-0F6A-45B8-90CC-05E50927D64E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7bc92e08faa2a642e2d8b65c07376e36b43f342","datavalue":{"value":{"entity-type":"item","numeric-id":435190,"id":"Q435190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8a2c6db5a23dea7fda1b43474516955941c7d08","datavalue":{"value":{"amount":"+0.8594843","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$C604A1EC-D210-4BC8-93EF-1D383D5CF481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b417248f164d120103a0cb16f0137e6e5af00970","datavalue":{"value":{"entity-type":"item","numeric-id":4263835,"id":"Q4263835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06938f9a111b6e9810763f6f32cc5a6215ad045c","datavalue":{"value":{"amount":"+0.8559257","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$98D08C71-37B9-4B0D-8E88-853791AA3414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7b47d5008fb5444114c966ed6f511fa02db28fb","datavalue":{"value":{"entity-type":"item","numeric-id":4790400,"id":"Q4790400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac604314402f396a4bd649fc381a8ed2d621f145","datavalue":{"value":{"amount":"+0.8550324","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$6AA8B3E3-EE9A-42AD-8D15-847050580CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ede333e06f1da3162b3a541fa4bbf91926fc13b5","datavalue":{"value":{"entity-type":"item","numeric-id":4873893,"id":"Q4873893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bb035cc8f4d284959634f81c6a30555d5655380","datavalue":{"value":{"amount":"+0.85503227","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2732273$4A52A062-A91C-493C-9F25-196891701E26","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cd9ebe56ec423ec5335930a0b1a45ca7ae3b5c0f","datavalue":{"value":{"entity-type":"item","numeric-id":6768298,"id":"Q6768298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2732273$2A2893B3-AF2B-4A8E-89E4-58CC0B7D46AE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2732273","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2732273"}}}}}