{"entities":{"Q306491":{"pageid":308258,"ns":120,"title":"Item:Q306491","lastrevid":52609760,"modified":"2026-01-23T02:35:59Z","type":"item","id":"Q306491","labels":{"en":{"language":"en","value":"Superpolynomial lower bounds for the \\((1+1)\\) EA on some easy combinatorial problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6621054"}},"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":"Q306491$D7D980C9-6AA7-4122-87C7-B943EABDB198","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3149f90255aff3095e9d2b075a1b534bb13bea94","datavalue":{"value":{"text":"Superpolynomial lower bounds for the \\((1+1)\\) EA on some easy combinatorial problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q306491$AF886C65-3E0C-4ED8-B8EA-D83C81816B98","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"48dfbaff8a16545d2d632f8876ca338f450ef4d9","datavalue":{"value":"1360.68791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q306491$A3ECA55C-2261-4548-9DA2-3E852AC215DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6297fe6a26ea390e74f41da137b643fd2d10964","datavalue":{"value":{"entity-type":"item","numeric-id":306490,"id":"Q306490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$4B7A8A23-AF6A-4CB8-AD18-541E8C502A12","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$32D3DA6F-82B3-4AA8-8AB9-FEEF6C06F2BF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bc9bb5292ab9421da6d217e259d9cc097ccf5c7c","datavalue":{"value":{"time":"+2016-08-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q306491$DFCD8A7F-B6F6-4266-B67D-0869FCBE307C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c3ed39756e1f29a6fbf3dcc947d1131c5b380d81","datavalue":{"value":"The author studies the (1+1)-evolutionary algorithm (that is, an evolutionary algorithm with population size 1 and mutation on this 1 element) using three classes of problems: finding 2-colourings of a class of bipartite graphs, solving satisfiable 2-CNF formulae, and solving satisfiable propositional Horn formulae. It is proved that the algorithm needs superpolynomial cost with high probability for all these three problems although the problems as such are polynomial.  The author is interested in understanding the structural properties of the problems that make the problems hard for evolutionary algorithms. In particular, he investigates when the algorithm becomes trapped in meta-stable states from which it has difficulty to escape. This is due to the so-called spin-flip symmetry, an invariant of the objective function under permutations on the alphabet. For the graph colouring the author gives illustrations which exemplify how the problems occur. The second problem class is isomorphic to the first, the last is different but shares properties with the first two. In order to come up with a better algorithm, the author modifies the algorithm to take into account domain-specific information and shows that by a minor modification the time complexity can be reduced from superpolynomial to polynomial.","type":"string"},"datatype":"string"},"type":"statement","id":"Q306491$D09586A8-9E06-4F1D-BFC4-8D7CBBD6E53D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"80e987276e122a41f9b91b8b2fac713fac5a8dbb","datavalue":{"value":{"entity-type":"item","numeric-id":504392,"id":"Q504392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$3550BBEF-1AFC-4719-8D4A-8A164B803AC2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q306491$6B473325-4D96-4A8C-A2AC-23BFA466C811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q306491$88DF2A0D-B158-45B3-BD08-AA843C50DE57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q306491$12FD0D49-C9E0-4C3B-8FC1-A6F7A0F6D669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q306491$FF0D861C-2EE8-4677-94E0-DA9E16C00FA6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e5cd64aff1e0903e0f4506c4816f3da0c0fd04d","datavalue":{"value":"6621054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q306491$847B2C41-DE0F-4524-9692-3C98DEC95554","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b59391821b915b007819c1a5ffb7262ad461b563","datavalue":{"value":"runtime analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q306491$C49E2F5F-D84D-4639-B836-969CC895DD2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q306491$A44610D1-D455-4E07-9828-3E4973157788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q306491$0D10A092-B521-4C9C-ABB6-3B147E45F322","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c308a7f01334c54ee3a347d2cf2e213f402011af","datavalue":{"value":"(1 + 1) EA","type":"string"},"datatype":"string"},"type":"statement","id":"Q306491$905370C2-D75F-46CF-83FC-9955990D1A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1c1138ee8f88731d90c2caf7af74450d82ac306","datavalue":{"value":"evolutionary algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q306491$844B03B5-A90D-457E-9DEC-A86DBE80C5AB","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":"Q306491$FE4FB553-5F65-4528-839F-55CD0EC16A42","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"48a3d8d3a76fe3faa892ea5b143d59eab14c18ce","datavalue":{"value":"https://doi.org/10.1007/s00453-015-0027-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q306491$508220BB-B523-4AD7-999D-E1831DC140B5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"32a04b7cb261ebf0753d0d68ed93c8a18548c7ae","datavalue":{"value":"W2468335684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q306491$41B35176-97B1-4E46-B670-0E94FA852A91","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$0234B849-ACD1-42EE-862B-7A1DBF1BF2D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac1780c549f1588d5e61afd650a82a9c88d2de51","datavalue":{"value":{"entity-type":"item","numeric-id":5306039,"id":"Q5306039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$2540994E-320A-45E1-8504-999310D514AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aad8cc9b1ac9554ff4a70a106dee8357520e9a2b","datavalue":{"value":{"entity-type":"item","numeric-id":5306365,"id":"Q5306365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$765C9A0E-F3A5-4D5D-8929-17CF7DDAB21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43a5463d80abce72f59514d0bcd58a0497b33908","datavalue":{"value":{"entity-type":"item","numeric-id":4289300,"id":"Q4289300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$933CC5F5-98AF-4038-80AB-A76B71BCEDC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32cda5d0a3b8d05e0e9e5fde7d20900ce7fd7ea4","datavalue":{"value":{"entity-type":"item","numeric-id":1945169,"id":"Q1945169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$73C3F0BC-87C7-4F0E-80EB-147FE3394C48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83cec570cc80fce899e06c899f00c12d0336b0a4","datavalue":{"value":{"entity-type":"item","numeric-id":2432545,"id":"Q2432545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$D70ADE48-E45E-40D9-9311-513EA4534D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c81516c6c39e3fc78cb2d96551922c2d992dcc0a","datavalue":{"value":{"entity-type":"item","numeric-id":5842911,"id":"Q5842911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$3716B7FE-35CF-4342-9366-882A7477A853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18239826148294315d2f3d91154b70b9b74ca51a","datavalue":{"value":{"entity-type":"item","numeric-id":633832,"id":"Q633832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$309FAE26-904C-4256-B22C-EE0BE780E2E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"193863feab4dfca97dbf1fd26a4db0b28881df32","datavalue":{"value":{"entity-type":"item","numeric-id":2575079,"id":"Q2575079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$B717D2F1-5EA0-4090-99C5-841E41423FA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc7f7c92aad7286bc7606d52413fb822b2b37a68","datavalue":{"value":{"entity-type":"item","numeric-id":4418669,"id":"Q4418669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$E71C76B2-FC6B-4188-A5ED-D27567427285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a077180a44e04e883e16ccc5d9ccde00dfe6a422","datavalue":{"value":{"entity-type":"item","numeric-id":606874,"id":"Q606874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$AACC7B28-3A16-4A79-99D1-127D78B5C705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"975751474c8fd4034c4ac3d9df143d1896cfb27f","datavalue":{"value":{"entity-type":"item","numeric-id":633834,"id":"Q633834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$570F2B27-3F5A-46D5-A2F9-BE0798560867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$9DE4EA9D-5763-40BF-B622-CFD1E58AD295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9c2550f2044f38e927ec98fa3c402888fe8ba32","datavalue":{"value":{"entity-type":"item","numeric-id":3997813,"id":"Q3997813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$E1F6308D-F4DF-451F-9E09-9DE69684D66F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ded905e05437f8f349d4b3409eb9bd9a4f16269","datavalue":{"value":{"entity-type":"item","numeric-id":4911174,"id":"Q4911174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q306491$3A918BA0-30FC-466C-8E17-E204DBC7DDE1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"530fda48dc0a6a37a3a542e7d47730ab797c0f17","datavalue":{"value":"10.1007/S00453-015-0027-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q306491$E84C335D-015B-4572-A4D5-F375B4634AEF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f80a059c69b64f3f704b7a03d996f0aee791d03","datavalue":{"value":{"entity-type":"item","numeric-id":1605304,"id":"Q1605304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0091950319cab621ed87bc68802e34048ae9d9bc","datavalue":{"value":{"amount":"+0.7492205500602722","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":"Q306491$A9689FAE-A61E-4053-95AB-53D3055C1736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"044ce0f71c066e19082ee0763231dcdee95bab7c","datavalue":{"value":{"entity-type":"item","numeric-id":3224103,"id":"Q3224103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"652c505ae848346c497ef6c85a0331118108eba5","datavalue":{"value":{"amount":"+0.7458093762397766","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":"Q306491$33A45717-7F0C-45D8-8AD9-2D2EAC2D4C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d9648c8708f94992f7c657fb719f01ad871929d","datavalue":{"value":{"entity-type":"item","numeric-id":2770499,"id":"Q2770499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c62296ae9c2eae2839c8d07a882cbedaa06ff806","datavalue":{"value":{"amount":"+0.744083821773529","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":"Q306491$0CA74A2D-B721-4510-BC42-84D8617A8CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c11a3880ccc46d47a3394a74a14913488f2f051a","datavalue":{"value":{"entity-type":"item","numeric-id":1775016,"id":"Q1775016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ef6e6490f66275a0678d2dd2e58025de6937f67","datavalue":{"value":{"amount":"+0.7310295701026917","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":"Q306491$99C023D8-C216-4EFB-BFC2-1094058BC293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a0353ab9b4be90d7d8a32e31aa8bbd0bef35a7f","datavalue":{"value":{"entity-type":"item","numeric-id":5215483,"id":"Q5215483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da5d63ffe22af7c11c722245016d8a739b5ce91f","datavalue":{"value":{"amount":"+0.7212703824043274","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":"Q306491$26181E8A-530B-45A2-853C-956D15DD608D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:306491","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:306491"}}}}}