{"entities":{"Q1260654":{"pageid":1271404,"ns":120,"title":"Item:Q1260654","lastrevid":67385358,"modified":"2026-04-12T17:16:16Z","type":"item","id":"Q1260654","labels":{"en":{"language":"en","value":"Witnesses for Boolean matrix multiplication and for transitive closure"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 370450"}},"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":"Q1260654$009545FA-32D1-47F3-AE74-F535DE2B4D11","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5f7055562f87fbf0c65f9850c2e1f30bcb305cf0","datavalue":{"value":{"text":"Witnesses for Boolean matrix multiplication and for transitive closure","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1260654$4B7A3C3C-7E6E-49E6-86EE-E13480B85E45","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"320b5e5dff05f46033fedd08bc073d243414e651","datavalue":{"value":"0785.65053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260654$DD668F5C-2A0C-4A28-A4C4-8F1115DB2C42","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0010b9eeb27c3605b204534d8f399950525bb6ea","datavalue":{"value":{"entity-type":"item","numeric-id":1260653,"id":"Q1260653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260654$E7E6610D-320D-406B-B65B-5DB132531C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e427d06588e0f5e6a2a228b1ad8e00160bd43819","datavalue":{"value":{"entity-type":"item","numeric-id":673782,"id":"Q673782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260654$919A93C6-729A-46FA-944A-6D8D5EC69950","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260654$968202FB-8B94-4564-B876-0A1FFE151F5E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63a2a2109a0646bfe8e8a3130f00ca3f280d500e","datavalue":{"value":{"time":"+1993-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1260654$EB25FAC7-549E-4C92-B903-B678CCA20938","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"114da06a29a8d870f55c49887b3eb6107b897dcd","datavalue":{"value":"The authors consider the Boolean matrix multiplication: \\(C = A\\cdot B\\), \\(C_{ij} = \\bigvee^ n_{k=1}(A_{ik}\\wedge B_{kj})\\). An index \\(k\\) such that \\(A_{ik}=B_{kj} = 1\\) is called a witness (for the fact that \\(C_{ij} = 1)\\). A deterministic algorithm is proposed for computing the matrix of witnesses in time \\(O(n^{\\omega+\\varepsilon})\\), for \\(\\omega \\leq 3\\), \\(\\varepsilon > 0\\). The problem of witnesses for Boolean matrix multiplication is related to the shortest paths problem. Also, an algorithm is proposed for computing witnesses for the transitive closure which has the same time complexity as the time needed to compute witnesses for Boolean matrix multiplication.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260654$6D367ADD-A45A-41E1-99EC-6559652448B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260654$E19DFE6D-1429-46BB-A8F0-B4D9299936FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260654$9A5F51EE-0E10-4FE4-BE82-D4F53A279852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06299a38dab9dd1c28e96fe2a7f8cac0943d746","datavalue":{"value":"15B36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260654$1D6AD4BC-584C-42FE-A0D4-8E58702382C2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"54c3cea69c68208e9e40df7d1fd074c122635ce8","datavalue":{"value":"370450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260654$7EB160A5-F0C1-4F0D-976E-A7BA5C981D69","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aba72f7a50c6331fc87e2da0e7087379a0bbc676","datavalue":{"value":"Boolean matrix multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260654$235BA694-E1EF-457B-87BF-6F068CB18C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"610a630ffab00b7233f7e3ba00b63a0c5e848bea","datavalue":{"value":"deterministic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260654$A2B43966-B3F6-4DD7-B16E-51CBF435F207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc653caf84375905a126daa3a69ac981b7ffe597","datavalue":{"value":"matrix of witnesses","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260654$B7E2D9C2-C2C9-4C0D-BAA5-F6B0CB0DE1F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a97fba398bd5c4a6d7bd72b191ee449a278ecc24","datavalue":{"value":"shortest paths problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260654$B901D227-22F9-4873-9A50-C6192B00DB46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2efd6ca2e632b6ca823bc98fefd73c07a1f518da","datavalue":{"value":"transitive closure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260654$D9D7BF89-F9FA-4290-B618-64E6AFEA6CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260654$E6E9210D-BD37-4422-AE35-9F0280FCFBA5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"32b61be5a8579cbff56f3ae053504391f67cfee3","datavalue":{"value":{"entity-type":"item","numeric-id":587430,"id":"Q587430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260654$1A63A178-3E4E-46B8-8B81-9A1ABD823707","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":"Q1260654$EA1953D7-8C4E-4DC7-B27A-1EBC13ED35F7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8d7f55904ca7301490d6fc715311b0e2b54c5458","datavalue":{"value":"https://doi.org/10.1006/jcom.1993.1014","type":"string"},"datatype":"url"},"type":"statement","id":"Q1260654$5CD6E548-4ED7-4D8C-A743-C5AEEDDF705A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c3e07ac4a6e88f0db259cc7a950884c217fb48ce","datavalue":{"value":"W1965216219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260654$68743462-A95F-4B8E-B914-F63886A8C2D5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"599b81cc3271499e9e677248cb5890fc2ea969ad","datavalue":{"value":"10.1006/JCOM.1993.1014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260654$0B2FE7DC-E78E-414A-BA0A-3271C30C0F50","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e40ae9d665af0a9902b147ec4326d89ab1002230","datavalue":{"value":{"entity-type":"item","numeric-id":4230366,"id":"Q4230366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fed4357e7b7b72d95c5cffe1fa3313e4e8f3ab4","datavalue":{"value":{"amount":"+0.92460084","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":"Q1260654$537E2697-E1C6-4FEF-ADDB-9219E659C641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29b30f090b3f5669668e58f9ddbd027c82d1717c","datavalue":{"value":{"entity-type":"item","numeric-id":517804,"id":"Q517804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34a24d753c5c12970ae87fcb6f7d04e46f23076b","datavalue":{"value":{"amount":"+0.9058046","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":"Q1260654$B526B20D-7F4C-4F48-AB7B-8830DF6D8E56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6603653117d278610947fdb0b8f5e9d7a089650c","datavalue":{"value":{"entity-type":"item","numeric-id":4634922,"id":"Q4634922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6a9fc401bb2b62eeaac82c91ed2bdd82d35a981","datavalue":{"value":{"amount":"+0.87241066","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":"Q1260654$7F98599F-3DF6-439F-A8F0-F1DFDBAF6555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2f3921150eb719c9a2fb7bc2b2d98caccc8d3c2","datavalue":{"value":{"entity-type":"item","numeric-id":761038,"id":"Q761038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92765b7e29497cb971a3bbbbdc43322f7a38729c","datavalue":{"value":{"amount":"+0.8526818","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":"Q1260654$B8E159F4-2FB0-441A-B0AE-1811AC9853D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a410ef688dd27ff880eb2f291a72733a1b78c4d1","datavalue":{"value":{"entity-type":"item","numeric-id":3454755,"id":"Q3454755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b06d1d8ef9e30c1e072074d4d9d0043bd3e764ec","datavalue":{"value":{"amount":"+0.8436842","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":"Q1260654$D5D766F8-36C3-4538-BF85-54AAE362ED93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d2502a1bfdf8aadcdd456f90bbbaf4f78b9719c","datavalue":{"value":{"entity-type":"item","numeric-id":2805475,"id":"Q2805475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11c7e3d196c8825f4b5953f36a3bb1635f9abef9","datavalue":{"value":{"amount":"+0.84135365","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":"Q1260654$62E345D7-5634-4768-B2E8-E3EE649B887A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a34a07c99c9b9a2e11a41ad0b459634ce02a7b0","datavalue":{"value":{"entity-type":"item","numeric-id":5507580,"id":"Q5507580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c9514b3af7d046998ef5015b3b8ed397c7e3e1f","datavalue":{"value":{"amount":"+0.8379137","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":"Q1260654$D446A545-BB81-4F2D-AA1D-3F00346FF0D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"408f814439a3ede33dd5bda714f016f4b36d8617","datavalue":{"value":{"entity-type":"item","numeric-id":5257755,"id":"Q5257755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceecd5200d08db88d6c6d3227a4965c89a84bcdb","datavalue":{"value":{"amount":"+0.8318435","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":"Q1260654$2235A6F9-B610-4470-94D9-5BBBA5395F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35251729edc4150d093993c4fdb177cdf8b94cef","datavalue":{"value":{"entity-type":"item","numeric-id":5432940,"id":"Q5432940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0df092ad8afb59fe09d57c25cb8ad7f17be67ee","datavalue":{"value":{"amount":"+0.8317572","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":"Q1260654$88C78D04-5AEC-4105-8C93-1C7029F543ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08f4ed61c852c1bca565c895726dc5c94f4b5ce8","datavalue":{"value":{"entity-type":"item","numeric-id":2663840,"id":"Q2663840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00019dc4371af2f2f2ac8ca211b1ce340265fd85","datavalue":{"value":{"amount":"+0.8308079","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":"Q1260654$9B491E7F-1533-41DB-9FF6-37C281DA2D7D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Witnesses for Boolean matrix multiplication and for transitive closure","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Witnesses_for_Boolean_matrix_multiplication_and_for_transitive_closure"}}}}}