{"entities":{"Q1314378":{"pageid":1325128,"ns":120,"title":"Item:Q1314378","lastrevid":46301553,"modified":"2025-12-24T12:55:43Z","type":"item","id":"Q1314378","labels":{"en":{"language":"en","value":"On space-efficient algorithms for certain NP-complete problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 501186"}},"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":"Q1314378$1653C396-9B43-497A-B7EC-02C321DD628F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9205c3809d72a4f5e643f47d28c9f1f3edfddb3a","datavalue":{"value":{"text":"On space-efficient algorithms for certain NP-complete problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1314378$3F83F765-A19C-4A5B-984C-F10056ECFFE8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82b4315fb58f67da182722d70cfd08efbce068d9","datavalue":{"value":"0807.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314378$CD453D4F-368E-4E4A-B16A-F3519A3B9C9B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"85e368167f872146c090140643b32c207785a4ad","datavalue":{"value":"10.1016/0304-3975(93)90295-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314378$642DF4A6-F084-43C4-93CC-9D2F1E45D551","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"24d2f620d2974ebdd1015229debd06431f4c7398","datavalue":{"value":{"entity-type":"item","numeric-id":1294575,"id":"Q1294575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$502161D1-0576-41E7-9DA6-8A05100A8B76","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$5CC5A1BC-1519-4AA0-8B50-BA3674EA6386","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e44c0ac4ec120779b28a294a0a11656dd7c52d04","datavalue":{"value":{"time":"+1995-03-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1314378$199143B7-4450-4826-B2B9-3C54CE168983","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7a2db1637f2f5158421961edaaaaf4177a3e60ed","datavalue":{"value":"In \\textit{J. Vysko\u010d} [ibid. 51, 221-227 (1987; Zbl 0642.68072)] existence of a class of algorithms solving certain NP-complete problems in \\(O (n^{1g k}2^{n/2})\\) time and \\(O(k2^{n/k})\\) space was claimed. Later, the claim was shown to be invalid by \\textit{M. Cosnard}, \\textit{J. Duprat} and \\textit{A. G. Ferreira} [ibid. 67, 115-120 (1989; Zbl 0678.68034)], and another algorithm supposedly having the same time and space bounds has been presented in \\textit{J. Vysko\u010d} [ibid. 70, No. 2, 273-274 (1990; Zbl 0701.68034)].   The article reviewed ends the sequence by showing that the approach advocated in Vysko\u010d's articles cannot yield to algorithms having simultaneously such time and space bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314378$C76F15EC-093D-4C9B-BC3D-1C01482A19E9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$85844268-497F-49E0-A341-791FA2A7A28C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314378$EB9E17F6-F3EC-4E4A-AFA5-49DE93FF9E85","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"58ea8a63e95ff769df28aa8b2d07c21e718205a1","datavalue":{"value":"501186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314378$14781784-59D1-42B4-B0E9-0E3FF9F07F7A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fc59007b2b1960a263350309435ca1e06e896b5","datavalue":{"value":"space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314378$FA9AFFD8-5794-4F2D-90DF-2FAD582E2FFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314378$EC81BC91-13AE-4E15-9022-5FF35A2B8080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e0c7481e3c5c308fc47ea6e648bd33e7ea295f7","datavalue":{"value":"searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314378$A024D6C9-3897-44B7-AFB6-F90DD2A1B996","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":"Q1314378$6A3CB1DF-BEB8-47E6-A4CB-D1B124D8E732","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e6ded2e10f241fad79d74bf19d55942060131418","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90295-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1314378$8BECD072-FC3E-4BEB-A08D-E2DBA46BEE0D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"52f13e8b3dbeead7268617c70b0d45ac2aa89ac8","datavalue":{"value":"W1979985963","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314378$BC988396-F2B6-4E41-8A7F-3A12FDAB5ED5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"68e9da6bbe094218079de58d2c81ce0af9c01bf8","datavalue":{"value":{"entity-type":"item","numeric-id":4088574,"id":"Q4088574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$667DEDF9-57AA-4B23-A059-CDDC7436F670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c59aec4aa99c0631b9aa7bf2c13df5f658b68d3f","datavalue":{"value":{"entity-type":"item","numeric-id":1124333,"id":"Q1124333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$92F6C713-6B16-49D1-A028-C16BC7DAC864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccf599651951ad1815ba272164667b6537d1837d","datavalue":{"value":{"entity-type":"item","numeric-id":911276,"id":"Q911276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$3FF15A98-ECBE-4538-88FA-2E20A19ECA67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8004eae2ffc5a942ba5a6e8374f263f0fbb9e96","datavalue":{"value":{"entity-type":"item","numeric-id":3912012,"id":"Q3912012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$4297861D-F290-452E-9C01-C27E6B7BD7C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb29e5566ff2d857954ca0b027f643322b531ba","datavalue":{"value":{"entity-type":"item","numeric-id":1101220,"id":"Q1101220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$EA4B33C3-69F5-416E-BCEE-A096F1E1A785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"002d6b402ee7e8d4b2ee69f9c74fc9e79978bd45","datavalue":{"value":{"entity-type":"item","numeric-id":914372,"id":"Q914372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314378$D8DCC2DA-04C5-4305-B832-2CD036826924","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75d25ab77c20f9c0a6bc63c29b51e042d0a538de","datavalue":{"value":{"entity-type":"item","numeric-id":1101220,"id":"Q1101220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"495e2983fdd1e8014a7d6bdcd0c7544bdc35e386","datavalue":{"value":{"amount":"+0.853646993637085","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":"Q1314378$4087A95E-5396-4998-9B98-63EE60761B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f99919881c264dc8529f965a4364ed9cb219a12","datavalue":{"value":{"entity-type":"item","numeric-id":3912012,"id":"Q3912012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d5fc9bff1baa783a7d3822529b23952423920c5","datavalue":{"value":{"amount":"+0.7944096326828003","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":"Q1314378$62CB26D1-2D45-4B8A-9FAF-9FCE52371C78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffe57791d26e5ef955c0025498296d702c55fc84","datavalue":{"value":{"entity-type":"item","numeric-id":914372,"id":"Q914372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1334e3bf9f7dac53128c463f965d60b3ecd40be4","datavalue":{"value":{"amount":"+0.7825753092765808","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":"Q1314378$29670AE8-9703-42C0-ADC0-74C883D3B70F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bf38cc888921590df143be54d6b97aac5f0ba8c","datavalue":{"value":{"entity-type":"item","numeric-id":4668733,"id":"Q4668733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a4ab4a01d8fb8ea9e6a5c836e138d5cb24f82cf","datavalue":{"value":{"amount":"+0.7644675970077515","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":"Q1314378$B3F908DB-29BC-458B-B15C-17859BD45F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a2c278c12254d1c744e0731d944d6d1736a4e72","datavalue":{"value":{"entity-type":"item","numeric-id":4938786,"id":"Q4938786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df32145de82f44c1e87c9747b0fd1c46c38f7bf5","datavalue":{"value":{"amount":"+0.7437136173248291","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":"Q1314378$E93E96A2-9AD6-4DFA-A148-DA0174DB4373","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1314378","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1314378"}}}}}