{"entities":{"Q4571928":{"pageid":6601517,"ns":120,"title":"Item:Q4571928","lastrevid":53133347,"modified":"2026-01-24T07:02:06Z","type":"item","id":"Q4571928","labels":{"en":{"language":"en","value":"Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6898319"}},"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":"Q4571928$4E9575C7-310A-4ADA-A868-4FDED84AAB47","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d08fc681dc998ca1bab623d1fb8b502034ac00ae","datavalue":{"value":{"text":"Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4571928$367B8C63-5DAF-4592-AD6A-3A9DC728595F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"454e26f41362475af97a44b3fbaed1532cfc0d4e","datavalue":{"value":"1396.68137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4571928$8BAF2220-A079-4F25-8146-A89FA6179BD9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d2eb247f691e272cc3eee24f9c4e078ab77e7465","datavalue":{"value":"10.1137/15M1053128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4571928$1F29856F-1A9D-49DA-ADCE-4EBBFE616719","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"619b3da40ce89470588c7f95a71532372f9ba3e6","datavalue":{"value":{"entity-type":"item","numeric-id":2843228,"id":"Q2843228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$ABFAFC17-32E8-461B-9D27-F6EC3F57FCBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7931955f1f617c7544e605edee3db1fe0846e3b","datavalue":{"value":{"entity-type":"item","numeric-id":732030,"id":"Q732030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$E410F70A-FFAD-4B44-BC1B-F83C61D200B3","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":"Q4571928$A55FAFE2-C10F-4E07-B535-393C5061625A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8a2469e9547180e8da9b9320d063ac8110297525","datavalue":{"value":{"time":"+2018-07-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4571928$F66DACBB-B0B8-4837-B009-AED01889D0E6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4571928$FA5159AF-CB29-4087-8E37-B081A82D6103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4571928$13967F3F-0FCE-40AA-BEF6-C67E474451D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4571928$9E3C4C88-2531-41D1-ADBE-38F4E39A8B7C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"02e81d07049be0be18d92d9d4fd2a2ff42b2b59c","datavalue":{"value":"6898319","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4571928$0289872E-D431-404B-B953-14464033BC95","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91c92c699214b9d1be7a56f31bd929aa164bb428","datavalue":{"value":"edit distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q4571928$E9DAD59B-F064-4159-B1C5-7B4008D8F836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78ac3261b77ce4fd3d632b98526dba4bf52e02f4","datavalue":{"value":"SETH","type":"string"},"datatype":"string"},"type":"statement","id":"Q4571928$3C6FD0D3-76FD-4947-AC64-C683C2107587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2450e02f50939b46b52c3140c8d1d485cebe36e5","datavalue":{"value":"pattern matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q4571928$F8D950E5-7EC6-4993-B288-EEBC5E8E110C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ee0444d0114e237dd2259a56cd881a78013bffb","datavalue":{"value":"conditional hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4571928$4253B632-343B-4059-91BD-93E2DDEB4A8D","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":"Q4571928$B1631BEF-31B6-40CD-A19D-2C65529394A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d49e6ab2d8acfa914ff18591de59648648d94f3d","datavalue":{"value":{"entity-type":"item","numeric-id":5361845,"id":"Q5361845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$32BD097A-45A9-43CF-B90A-D28FCF80B1B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73c7cec10f75f37a3d3ec5336df6610144935b32","datavalue":{"value":{"entity-type":"item","numeric-id":4933374,"id":"Q4933374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$E976C1E7-1EEE-4415-9145-306CACF27EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d72a926ee1823df1941e14c10b12be1badbee4bb","datavalue":{"value":{"entity-type":"item","numeric-id":5167729,"id":"Q5167729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$B7C7D932-2BC1-478B-B094-F89428C67971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f170ea76fa033beee3cf828d257c06a919a41e62","datavalue":{"value":{"entity-type":"item","numeric-id":5363029,"id":"Q5363029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$6BA11749-138B-4D29-90D8-BA36BF5492C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f481e2b5ac6958d6d77c3d219d87aa2d6d161897","datavalue":{"value":{"entity-type":"item","numeric-id":4575668,"id":"Q4575668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$DFFE6533-78E2-403B-A3FE-955D6506A232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"112fa1e16c28072d1b690d88a68f10e9a878f19f","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$4883BA9E-1121-4BE6-A4A4-A6F91711386B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4548ea5d583917c0fa9b6aaa6b1d48c80c1e7e","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$9AA728E8-AD8D-4654-A025-647B6B335FCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc28553cbd079f414114c265d86a94b6ad484595","datavalue":{"value":{"entity-type":"item","numeric-id":1140994,"id":"Q1140994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$A9B7B262-A417-4FB9-BE77-21BE7A0B19A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4226e3e65547158ea8072512457653ecc8bcdac6","datavalue":{"value":{"entity-type":"item","numeric-id":5417690,"id":"Q5417690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$931CAE7A-3D5F-409D-A171-4162DCDA8564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4675fdb0e0708f4f0cc371668bf4c2847e859377","datavalue":{"value":{"entity-type":"item","numeric-id":5495822,"id":"Q5495822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$BB905377-1623-4F05-AB26-1B3D9143022F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf6a72a62eb7ac00a65cb3378a54949f41ee0676","datavalue":{"value":{"entity-type":"item","numeric-id":2581276,"id":"Q2581276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$F507BD61-8EE6-4E09-9684-C27717EF69A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a205af6decd0ce6e8156191a3f954fe4c0288c3e","datavalue":{"value":{"entity-type":"item","numeric-id":5363756,"id":"Q5363756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4571928$07053ECE-B3F4-4BDC-ABA4-0B3C47389D11","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"889622f4d251fe51d11b568e6450490eb5a422f8","datavalue":{"value":"Q129647625","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4571928$5DC33D52-10CE-41EE-8D4F-BBDC65E6C75F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"176bbe79208eeb14dfce3938ac0ccc72d0b0a189","datavalue":{"value":{"entity-type":"item","numeric-id":2941488,"id":"Q2941488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3089b63f699084d2116806a91c8bee2730b2b46c","datavalue":{"value":{"amount":"+0.9885501861572266","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":"Q4571928$D7BAB32D-6E1A-4D22-B1E9-C2D8A255D0BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7513c844a4dc1c0d53b49357a70abf67bdbbd9c","datavalue":{"value":{"entity-type":"item","numeric-id":5056449,"id":"Q5056449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c87d872cc798dd85e0dfdbd0ed5133f3693fa9e","datavalue":{"value":{"amount":"+0.8552030920982361","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":"Q4571928$F61592F3-AC9A-460C-B031-8DF813BF09AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"977f40b0ff6ba05d045f3ac21de33c5ca8169574","datavalue":{"value":{"entity-type":"item","numeric-id":5172713,"id":"Q5172713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"334f680548b5697037c8a56178b4fdf57de4e4f9","datavalue":{"value":{"amount":"+0.8237097263336182","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":"Q4571928$F4E01E60-16D4-473E-99F9-42909CF3B552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c139153c3053980e8e0a6d476fa66ef309d1afe1","datavalue":{"value":{"entity-type":"item","numeric-id":4910578,"id":"Q4910578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd64690bff77ef191259021c469502528879c6cd","datavalue":{"value":{"amount":"+0.8233655095100403","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":"Q4571928$64E50E53-CA41-4A72-B6CC-BFCF9E907F9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7db843e22d11e0423c1f2dfa47f18e1331e92dc0","datavalue":{"value":{"entity-type":"item","numeric-id":1107330,"id":"Q1107330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee62afbf756302bc29783a697b2e4877c2b689db","datavalue":{"value":{"amount":"+0.8125612139701843","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":"Q4571928$24421181-CCA5-4B8A-B0F4-D752E6A05270","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4571928","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4571928"}}}}}