{"entities":{"Q626686":{"pageid":628533,"ns":120,"title":"Item:Q626686","lastrevid":63071391,"modified":"2026-04-11T10:24:13Z","type":"item","id":"Q626686","labels":{"en":{"language":"en","value":"Random CNF's are hard for the polynomial calculus"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5853292"}},"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":"Q626686$D6C41C6E-83B3-4FED-97FF-0C0FED996B2E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"69accbb249e71cb0566a2d089f5edabcbb97d17a","datavalue":{"value":{"text":"Random CNF's are hard for the polynomial calculus","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q626686$2FA267DF-68C1-4A3C-AE94-005066A9DAF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"12af5b054db32b610e9a67932d11b3e3c36735b8","datavalue":{"value":"1216.03064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q626686$E20C6354-8DCC-4FC8-8032-48CBA0463ED4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5dd3094b0d0097c1754f63d55999ed1b4931a5c0","datavalue":{"value":{"entity-type":"item","numeric-id":496302,"id":"Q496302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q626686$79A98226-C6FA-4DE2-99CC-D880C5D2A937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afbdf0b4b75e6a0dfd1ecc76c9480c04f5fced5d","datavalue":{"value":{"entity-type":"item","numeric-id":202088,"id":"Q202088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q626686$AE77050C-6667-4049-96F0-10EDFF3EF585","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q626686$0952791C-B533-4C7B-B00E-284234BAB14F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2131c0f950d0fd8541c671c480aa077e7869a9e9","datavalue":{"value":{"time":"+2011-02-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q626686$F148B3B6-BB73-4069-8691-A59D883D9D71","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q626686$A8F9A630-46FF-40E8-86E3-63699DD8C07B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"419d6f2b09c39920e34f63114ff159a2f0a01812","datavalue":{"value":"03B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q626686$E02DE379-2308-4A36-A4C6-0A1B87D2B492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q626686$2C96AFCF-E2BB-4A23-AF07-DB6A775824A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q626686$0EADC570-37E9-4A99-A3B2-117E3BA4BD9B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"715cf6ea2286169b233810eea40e640a29a14d3b","datavalue":{"value":"5853292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q626686$7F14FFC3-5B79-40E4-BB5C-F3963856B54D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"beacc345177607df4ab1f59f0170626c9d1a1d90","datavalue":{"value":"propositional proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q626686$D03D32A3-8BB9-4833-A69B-C3470E2F04A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211f3c345d1c27387d231726f7e79d65298863cc","datavalue":{"value":"polynomial calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q626686$78EC689D-1E14-4681-BCDA-1079A6DCF7C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bae09195fd611bccf15c25e209f2742706bae66d","datavalue":{"value":"Gr\u00f6bner basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q626686$D30E632E-0FA5-4547-B7E6-0DE58E72C00D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e38f742c27c8c48f80fdf9d57b86fa89ec081731","datavalue":{"value":"random CNF formulae","type":"string"},"datatype":"string"},"type":"statement","id":"Q626686$66BE9AD2-CAE0-4826-B156-D4BFCA8F8527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q626686$E33DE168-C163-42A1-95CF-A9D5B647F62B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66c29fdd432ad437c4c1ed1a5361ce53fc9bfd6b","datavalue":{"value":"refutation-degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q626686$50945C60-A5AB-4DA9-823D-7D27AEB69A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca020ba32503967454846f7aa97b9d60357002d8","datavalue":{"value":"Gaussian width","type":"string"},"datatype":"string"},"type":"statement","id":"Q626686$097D222F-47DE-429B-B507-7E49A4A7BE31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"253767ae60d9b83a6cbe15d31236cf3b1adf9738","datavalue":{"value":"complexity of refuting unsatisfiable systems of linear equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q626686$79349D02-0875-4E54-AD97-F57713E6E7A1","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":"Q626686$9E9C2E0D-86A2-460F-B0A2-29DEB019E4A4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f6c325e67c51cc1480da43519de6f07d45db060e","datavalue":{"value":"https://doi.org/10.1007/s00037-010-0293-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q626686$3213CC74-98BD-406C-825D-8E527EFB8B86","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3fa2178c97172e876ce8854c0950e1e5b0b946c6","datavalue":{"value":"W2139212134","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q626686$DBBA193E-5B98-47DE-BB7E-5143B501E6E1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f30ba2e1148b42702f0612e46cb63947a468e21","datavalue":{"value":"10.1007/S00037-010-0293-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q626686$A90703D6-0869-4779-85E1-89F2F815FB9F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e56f6cc49e8babb67d365ccbe97ecae50ca12879","datavalue":{"value":{"entity-type":"item","numeric-id":2255289,"id":"Q2255289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0eeb9b6a313132a40cb740f3138c7b0ee37b0c91","datavalue":{"value":{"amount":"+0.88688904","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":"Q626686$203452CC-9AC4-49F5-89B4-6E360DD2125B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bab13ab1318a08788452fc136c91b04b5ecff2f3","datavalue":{"value":{"entity-type":"item","numeric-id":3031835,"id":"Q3031835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d063d38d831bcb2aec017954566173a5e250ea92","datavalue":{"value":{"amount":"+0.86400604","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":"Q626686$00B45A5D-CF69-4FA0-AE4B-34455824B53D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e6d27e9c44e51cd9b30063f611cd0352e58336a","datavalue":{"value":{"entity-type":"item","numeric-id":4542576,"id":"Q4542576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42d8cadba35c41308b802091f1a9703661f494e8","datavalue":{"value":{"amount":"+0.8591228","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":"Q626686$F2F23E23-6A0A-48B3-95B4-D2C8D7E08B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd519b097c8856e989f95ced03415a7bc996161a","datavalue":{"value":{"entity-type":"item","numeric-id":5096442,"id":"Q5096442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00a904d13272976fe7064d70564ea3dcc121aab5","datavalue":{"value":{"amount":"+0.85340154","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":"Q626686$373CF088-CD1F-4CF1-85AE-7E5DEACFDB0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f746d4ca1e436a39ff7b879bc97cdc3a2ef13973","datavalue":{"value":{"entity-type":"item","numeric-id":1917082,"id":"Q1917082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5d943dab7ca42a016a2d255e2daae9adef92fe5","datavalue":{"value":{"amount":"+0.85190904","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":"Q626686$7EBB71D4-B2D8-40A0-B6FB-B205FC77CC26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2a8be6cb45c75c371834e01aba0791044f64701","datavalue":{"value":{"entity-type":"item","numeric-id":4525683,"id":"Q4525683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e70220779888c236d301affe90820e95847f606b","datavalue":{"value":{"amount":"+0.851909","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":"Q626686$39DB6853-9556-4192-99D1-39B7DE08068B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9a4a9e9f5e8aa25df337aefed053db314f25aba","datavalue":{"value":{"entity-type":"item","numeric-id":4723714,"id":"Q4723714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d5579a90bb0a19739bc01fd891d065c606e3fcf","datavalue":{"value":{"amount":"+0.84955883","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":"Q626686$71A1A295-B903-4F0F-8621-0758C44EBA38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d72dd764f71d38ba62a6233e6ba56d33c25a41b1","datavalue":{"value":{"entity-type":"item","numeric-id":3773343,"id":"Q3773343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f09d57dcd357fef74de232fa0cc18cba67880b6d","datavalue":{"value":{"amount":"+0.8485054","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":"Q626686$4BF15BF1-A2DF-476C-8A90-224298F0F1C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"559b3bb45ec2ed9fe95b3cf5242bee536ce943b7","datavalue":{"value":{"entity-type":"item","numeric-id":4942045,"id":"Q4942045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cfa51689a713cec04e037c5b799dca48f9b339b","datavalue":{"value":{"amount":"+0.84821486","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":"Q626686$4D9F5231-A715-4F57-9892-8D3F2867A9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cab4578cbbbb632d8c39fa70b613279d0aa1378","datavalue":{"value":{"entity-type":"item","numeric-id":4520323,"id":"Q4520323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cfa51689a713cec04e037c5b799dca48f9b339b","datavalue":{"value":{"amount":"+0.84821486","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":"Q626686$98914905-51BE-4AC2-9458-22D3DAA18450","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Random CNF's are hard for the polynomial calculus","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Random_CNF%27s_are_hard_for_the_polynomial_calculus"}}}}}