{"entities":{"Q1028148":{"pageid":1029996,"ns":120,"title":"Item:Q1028148","lastrevid":69454983,"modified":"2026-04-13T07:06:49Z","type":"item","id":"Q1028148","labels":{"en":{"language":"en","value":"Using clausal graphs to determine the computational complexity of \\(k\\)-bounded positive one-in-three SAT"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5572011"}},"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":"Q1028148$7E543339-14D1-4CEA-A8E8-7CAD6BF58FD7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"123386d1b88ec825cffcb9878bd27e5da8efba85","datavalue":{"value":{"text":"Using clausal graphs to determine the computational complexity of \\(k\\)-bounded positive one-in-three SAT","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1028148$C9C06425-0DFE-4BC7-B0F9-4D3B04A0D19B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1a1ddee88c3891d28918f300791650b939ef3381","datavalue":{"value":"1186.68218","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028148$2160EDD8-E9AD-4E18-808E-3B1CD871787C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf8049e1b9d4d05ee83b6626c8be5de961e628bc","datavalue":{"value":{"entity-type":"item","numeric-id":1028147,"id":"Q1028147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028148$3375BF01-1EB8-43C0-96C4-6E84E6307BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1539b067993f0145d4640934645063f84bed9fff","datavalue":{"value":{"entity-type":"item","numeric-id":1083720,"id":"Q1083720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028148$635794E5-31B0-4144-AFB0-A58E02642502","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028148$1CE10660-ECE5-42DD-B2F6-843B10FB13B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"09df791b31880a83cb69102ced8fef72b45dd8e8","datavalue":{"value":{"time":"+2009-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1028148$2BF0B977-8169-454A-816B-E3278C7392CA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028148$9FFFA11C-5050-445E-9257-DB3644457FD4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"04a960d6293abad67cf502b18afbc8ee07bb0f8d","datavalue":{"value":"5572011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028148$53D00346-DA26-4A6B-8C42-383AD96BB7C7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d38b775c320efde2b29aa637ee4c015b49862d87","datavalue":{"value":"one-in-three SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q1028148$E48CBE50-05DE-44F7-BFB0-624969C7BC9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee654aac6a0d9da5df17d70efce7bf7888d3b115","datavalue":{"value":"clausal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1028148$6377548E-F50F-446F-9416-87DCC4D01B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"267b394071cf1b5b643cd515aabcdbcae8c08f98","datavalue":{"value":"polynomial complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1028148$4DECF9FB-B265-4803-AC45-1EECD377FC15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d50df7f38d1685fbf9378fb5be538e17a3b733d4","datavalue":{"value":"nondeterministic polynomial complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1028148$77902D64-BC2D-47F5-B2B0-1B94CE7710C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1028148$7C548682-08B9-4724-B7C3-B3137FAD8F26","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":"Q1028148$D9F2B056-6356-4065-8F57-A73897396576","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8dc11554e108a850538ac6056ccdce9535ac9c91","datavalue":{"value":"https://doi.org/10.1016/j.dam.2008.09.011","type":"string"},"datatype":"url"},"type":"statement","id":"Q1028148$9BEB0AA2-362C-4370-9D62-7E3946FD1C70","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"26c09cb4d24c79253b3820091caa4a09a0f3c796","datavalue":{"value":"W2100367658","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028148$A958A913-7500-45EF-81C4-ACB4069B5441","rank":"normal"}],"P223":[{"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":"Q1028148$A611E9FE-34CC-4527-BDE9-67B0EFB28081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028148$6E834D5B-7B6D-4425-AFCF-62B85E324A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50041fd827b9a880db5475227f379529c471731","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028148$BFAA438E-5151-47FC-9E74-951F2AA8FB31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fe40a2b096be64684307fc706482845a394ed0e","datavalue":{"value":{"entity-type":"item","numeric-id":875598,"id":"Q875598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028148$85857307-242C-4B62-9E13-49326A0C5EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028148$B864AF64-89AF-4D2F-9795-4EBA1CF60C88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f61c5d68d33f8ea7723f3ac70afbbc88052e3402","datavalue":{"value":{"entity-type":"item","numeric-id":3258697,"id":"Q3258697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1028148$C6F57DEC-6E25-4483-B1D4-6497AEBE9570","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2d10d9826edeec94f1444d2ca579f2daaecc0be4","datavalue":{"value":"10.1016/J.DAM.2008.09.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1028148$B61265E8-D89A-433B-8A5E-6B9960FBAFD8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55782ea698f1f7994f85db0053bc8d9657b86472","datavalue":{"value":{"entity-type":"item","numeric-id":875598,"id":"Q875598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3cbb203f4cbc0eaebc642a0716e7060b18add4b","datavalue":{"value":{"amount":"+0.797225296497345","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":"Q1028148$8B55F793-D08D-40A2-AD1E-91CFD02C9273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5474d94e077936d6ac91cde4b55e3d28cae7011","datavalue":{"value":{"entity-type":"item","numeric-id":2223685,"id":"Q2223685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a7c03bf371fc2ec0cbf9af626247d784afcd093","datavalue":{"value":{"amount":"+0.7950663566589355","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":"Q1028148$E52C4FBD-3892-4B86-BCB1-4971D8B07F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"438ca1492819dc9e73a8c603ef8ddaa7f71a92bf","datavalue":{"value":{"entity-type":"item","numeric-id":4032119,"id":"Q4032119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78c83444a763d63eb87c119ca8c43a07716cb807","datavalue":{"value":{"amount":"+0.7909846305847168","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":"Q1028148$E19D3CA7-C129-4DF7-B392-B819A7BF010D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2608de4f95690f91de4a7ab9bdf7bfca1e1ee77","datavalue":{"value":{"entity-type":"item","numeric-id":4963262,"id":"Q4963262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c06bf46cd9a87b21b0aca96b85ac3473e76ebdc","datavalue":{"value":{"amount":"+0.7892077565193176","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":"Q1028148$87A32F9C-34B4-419F-ADE9-B89D7B0505A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df684ab8201b649acc8d339dca420dbf8bf70615","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bfc0a1b5e9acde2f92bf74052a4d478766f557f","datavalue":{"value":{"amount":"+0.7869035601615906","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":"Q1028148$D6060062-5CF6-4402-BEC0-1EE850B0E11E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Using clausal graphs to determine the computational complexity of \\(k\\)-bounded positive one-in-three SAT","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Using_clausal_graphs_to_determine_the_computational_complexity_of_%5C(k%5C)-bounded_positive_one-in-three_SAT"}}}}}