{"entities":{"Q4037693":{"pageid":6067411,"ns":120,"title":"Item:Q4037693","lastrevid":55240369,"modified":"2026-02-05T05:21:43Z","type":"item","id":"Q4037693","labels":{"en":{"language":"en","value":"One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 169009"}},"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":"Q4037693$345BB766-310C-43C2-9131-D9BC1DE73F5C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0291ff808e3b21057762f654f518858aaf5cd101","datavalue":{"value":{"text":"One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4037693$4BCF5C82-6863-493C-BD60-1A8F81CC921E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d6ec468e903a04613e76ddcb0db15de814ca3e49","datavalue":{"value":"0767.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4037693$9CDC0F66-DB1E-44AA-B40B-9EB95120C3E2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"446c776e016898901efe3662f826fd8db815b810","datavalue":{"value":"10.1137/0222015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4037693$CB5B0597-6D67-4C75-BC96-57FFED087DC8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9034d743abb2e8189da1fd67afac14b0cf3088f3","datavalue":{"value":{"entity-type":"item","numeric-id":175587,"id":"Q175587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4037693$4925F55D-A8CE-4D16-A29A-DE9915A573D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3130e87f1749c59ee4d0e395d449a1e09007fc09","datavalue":{"value":{"entity-type":"item","numeric-id":278738,"id":"Q278738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4037693$9AC2B779-72B7-4E04-94C5-9C1BDA9F964F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4037693$F5F2D032-AC9D-4DCD-8DBB-2BF599F7D1BB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4037693$247A00FF-1C05-4607-9ABC-9215F8ACCF9A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4037693$20E0F2BC-73CF-4786-AAD1-85820E1748B9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4037693$FA2B0BC8-A99C-4BF5-BE03-1E9D4E814C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4037693$D9762F45-7943-4535-B4AC-21F6FA3EE695","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2599819e698d9d30e38f9cf8e8f05a0628f6db00","datavalue":{"value":"169009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4037693$84FF5F73-496B-4DD8-90F5-A9D25804F088","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4037693$949EBFCA-DC0F-407A-ACBC-7722F1FB139C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c28c97778fbb68f4b3d21d002e4e8a64c7d17bf","datavalue":{"value":"Boolean formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q4037693$FFD5B81D-7CF1-4B61-8931-76D039720EBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"828e479c39c5c64293eb95e0403dbef7bbf79066","datavalue":{"value":"conjunctive normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q4037693$749D90E6-8ADE-4926-A6B0-E4EF8A55253F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4037693$955564F5-7977-41B5-A63E-3A45EC5BB8BF","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":"Q4037693$F74C66F2-AA7F-4726-B478-047E911E679B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"554bc15f53a6f072566190c845ee2925a63cdaea","datavalue":{"value":"https://doi.org/10.1137/0222015","type":"string"},"datatype":"url"},"type":"statement","id":"Q4037693$509692EB-03BB-4E47-A1B3-6B69AFE8ADE1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"893151bd5f114b6a07b41cff3ac07b8a32aa5ab4","datavalue":{"value":"W2000171675","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4037693$45020101-B9A7-4D06-A16A-35EB69551DFC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26b97ba761d4e2b6ccde57061d1068fe5c8a35ef","datavalue":{"value":{"entity-type":"item","numeric-id":3440269,"id":"Q3440269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f75a5d31eb85624ccba47941662a2ecb9b62f493","datavalue":{"value":{"amount":"+0.8679629564285278","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":"Q4037693$8B2379F4-FCC0-4DCF-85DA-294A91101D7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24ec9455f54c32283ad7953bf6c8ed6237e5816a","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d31526c08c76eed73ab2635d7be862722c2e0a4d","datavalue":{"value":{"amount":"+0.8519536852836609","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":"Q4037693$E0D7C1A7-1858-4976-BD18-9F37FD2FA75A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20fc3c596a9edb8e5583cac032889717c67ce3fc","datavalue":{"value":{"entity-type":"item","numeric-id":1711421,"id":"Q1711421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf07befd66022d9320e9f7a247a7e3315beb7fa1","datavalue":{"value":{"amount":"+0.8437554836273193","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":"Q4037693$495B64C8-5B16-4127-918A-0CD609CA9789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a00557940f92d8bb4109ce8bce395883cc753d4","datavalue":{"value":{"entity-type":"item","numeric-id":1322290,"id":"Q1322290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41f8e3d974ca724b3824a571fe26a394511b4fea","datavalue":{"value":{"amount":"+0.8384251594543457","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":"Q4037693$7F209CD0-5D31-433D-A276-C3E364713D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6456c7d409da6b9e2de61a1cd646ae0a609b5f2","datavalue":{"value":{"entity-type":"item","numeric-id":4930606,"id":"Q4930606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b3549ddea71454ca567f68eb21dd63e08bdf61f","datavalue":{"value":{"amount":"+0.8345277309417725","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":"Q4037693$23056A37-A734-4C6F-B563-CDB397B13862","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4037693","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4037693"}}}}}