{"entities":{"Q1777401":{"pageid":1788143,"ns":120,"title":"Item:Q1777401","lastrevid":48484486,"modified":"2026-01-04T23:25:48Z","type":"item","id":"Q1777401","labels":{"en":{"language":"en","value":"Exact 3-satisfiability is decidable in time \\(O(2^{0.16254 n})\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2168191"}},"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":"Q1777401$08D051FB-B2E7-4D3D-ACE6-1A41CEF9D64A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"780b741fb541578bae9450db57da9fb522c23ba3","datavalue":{"value":{"text":"Exact 3-satisfiability is decidable in time \\(O(2^{0.16254 n})\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1777401$F03218CE-7222-49FC-999F-3F64B76C49CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c8857106f26bc33f06a47b0949a97ef9f847f77a","datavalue":{"value":"1099.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777401$EF60DBB4-5AF6-4DE7-9715-F1621AB77AFD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ffb0466461e16e203e1eebcf15c374dbae0d4e8d","datavalue":{"value":{"entity-type":"item","numeric-id":714019,"id":"Q714019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777401$1E6F5323-A52C-4F70-81A3-41C0EDC73CE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e6879434540b31e0f3562b59343a4081818cc9a","datavalue":{"value":{"entity-type":"item","numeric-id":708333,"id":"Q708333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777401$6AC4A7D8-E5D5-4682-8105-33F1D052A42C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a52c13955159b7796643777df723759736e16f2","datavalue":{"value":{"entity-type":"item","numeric-id":714018,"id":"Q714018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777401$3D6C550A-98A5-480B-B8EF-CCC76816FB01","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7346dc34d1d50fea46ec345fbc7e3214530889ab","datavalue":{"value":{"entity-type":"item","numeric-id":276517,"id":"Q276517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777401$C76CDB43-2DFA-40BB-8658-8E0687460495","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c64595f4f39ba5aa8c317730455f9500451c9c2e","datavalue":{"value":{"time":"+2005-05-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":"Q1777401$ACBE0BFB-C779-492C-B2D1-6AD68BEAFB4C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777401$5F9452CC-D516-4130-B9C4-2F4BA081C943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"419d6f2b09c39920e34f63114ff159a2f0a01812","datavalue":{"value":"03B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777401$6B54821A-B893-46EA-AD65-4D84F365B429","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777401$2BD46EA4-444B-4E89-A2FA-C3A684E52945","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3295986076cc903aab433150f39133df5450d92c","datavalue":{"value":"2168191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777401$BAC52EC7-ADE1-47BC-A345-6483E485715D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26d6437e70c0f6668cc0637d82ae9f51a58b6e7a","datavalue":{"value":"exact satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777401$A8C756C4-E0D8-46F3-B7E7-51FB89C64C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b68c56f1fd739688bb6921d59ab100c3ca188e7a","datavalue":{"value":"autonomous clause pattern","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777401$FC5856FE-9CDC-441E-98B9-3350E61D212D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b10e178454bd9f310ac6a04b7e09c4e9bd5df69","datavalue":{"value":"formula graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777401$F9C50D44-991A-4C9B-8FF8-3A53A03D8773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777401$E441E7B2-B88F-4113-B99E-3408E2A18E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1777401$1A3404C1-0DFC-46E2-B7FB-B0F6B28EBF58","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":"Q1777401$C238D73C-6862-4592-98D0-D7E25B10BC4B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9f8a0b6f3512e6341dd016433d7564f9e445b32","datavalue":{"value":"https://doi.org/10.1007/s10472-005-0428-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1777401$C647C66F-28E6-4432-ACAA-96F4D0177BB8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fd88024bae98374bfbb8928e6b0f41f7ec0f950f","datavalue":{"value":"W2474390896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777401$83AF7E6A-7F38-4E17-81D3-17E0431F3012","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"be1c16314d571ac552ffc4dba48f547b3438465b","datavalue":{"value":{"entity-type":"item","numeric-id":4747916,"id":"Q4747916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777401$B55D68BC-FF02-46F1-B257-82744AD263D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70db900b6090c78b5dac2fd4eb7b2a92dc327434","datavalue":{"value":{"entity-type":"item","numeric-id":4938786,"id":"Q4938786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777401$3CBFBE48-1247-4E11-B6B3-44939CB70588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777401$9A330C4F-DF79-4959-808B-3E8C9092DB92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1777401$73C61AE8-2E58-4558-9947-6230813673D3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"255ce13be3cb081672eb728243bb597a0ad8e198","datavalue":{"value":"10.1007/S10472-005-0428-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1777401$802CA461-7572-450C-B407-853869FC5EE5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"501efdd6431b5a19076722dc325d27a324763638","datavalue":{"value":{"entity-type":"item","numeric-id":2577590,"id":"Q2577590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea3dba7e17d9ee427dad747d5a23f8c4af2f4afc","datavalue":{"value":{"amount":"+0.8940811157226562","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":"Q1777401$FBC27FAE-E15A-4BE8-B271-589CF1515E9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e69c1864d8d72ba106a26af3be9f669bbb1df736","datavalue":{"value":{"entity-type":"item","numeric-id":1770407,"id":"Q1770407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36d44c8782ac8161b8658ab611683676ef4a343a","datavalue":{"value":{"amount":"+0.8658588528633118","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":"Q1777401$B1DDAD30-80EF-4096-AEFE-04845282AA3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a10d3afb1955d15139cbb29aeaee1ac969582928","datavalue":{"value":{"entity-type":"item","numeric-id":2897996,"id":"Q2897996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7847d9c032f8332b0181e5f373aff6868888a372","datavalue":{"value":{"amount":"+0.8317195177078247","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":"Q1777401$2E32F4D3-E976-462B-AD7A-978C7029401A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f68dd49e8d790217f4c6e141204af1920c329f5f","datavalue":{"value":{"entity-type":"item","numeric-id":4283247,"id":"Q4283247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82d87eca4866b3dfb1b0eb1ee015950083d80b81","datavalue":{"value":{"amount":"+0.8251705765724182","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":"Q1777401$59D7A846-D934-4341-9EC5-B196DE3518D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a656f063de935ced5cb23a06c4a0b1791f8e1531","datavalue":{"value":{"entity-type":"item","numeric-id":596105,"id":"Q596105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2d83f0cccabf8fd008b59a2c2eb0f57a2d0e8a0","datavalue":{"value":{"amount":"+0.8249438405036926","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":"Q1777401$1F0408C3-BEA6-4CCF-AB7D-B8B9D8391B39","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1777401","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1777401"}}}}}