{"entities":{"Q2173301":{"pageid":2184044,"ns":120,"title":"Item:Q2173301","lastrevid":53715002,"modified":"2026-01-25T14:45:26Z","type":"item","id":"Q2173301","labels":{"en":{"language":"en","value":"A new algorithm design technique for hard problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7191865"}},"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":"Q2173301$8B074C50-5878-444E-AA32-3CE2DBC899BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1abc0b9f28d47f1f64eafe015fbbe015806461da","datavalue":{"value":{"text":"A new algorithm design technique for hard problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2173301$60CE5192-311F-4096-96CF-A4C16CBF667C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f940be6beb1ffc67c534a1bfa2f15c87fd67f05","datavalue":{"value":"1448.68464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2173301$2B06C762-5189-41C8-B516-87FDBE0E6BC3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e8b17d77e00a3a292365f4093936b4e576be792","datavalue":{"value":{"entity-type":"item","numeric-id":1736820,"id":"Q1736820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$DE8217FF-65BD-4EB9-8526-5987DBBF7646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"844d5030b1fc513f5d0b93ac262e3a245096053d","datavalue":{"value":{"entity-type":"item","numeric-id":924145,"id":"Q924145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$903D27A1-58F5-4D68-9DDA-7616D15C5B66","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":"Q2173301$05A8A027-710A-4012-B38F-89B7309659DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"72ee0f65bfad3851f3cc10baace260313082bce5","datavalue":{"value":{"time":"+2020-04-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2173301$9F266395-80D9-4AA3-8E29-9945A318908D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0678a93e002bd703cb5d16429de49a25d05e2121","datavalue":{"value":"This article presents a new measure for assessing heuristic algorithms, which considers the possibility that the algorithm does not produce any decision at all, in addition to the possibility of producing an suboptimal one. The first two sections present the background notations and definitions, including errorless heuristics, failure rate, roughly polynomial time and paddable language. The main result of the paper follows next, which considers the roughly polynomial time of paddable languages. The article concludes with a proposal for design of algorithms which uses the proof of the main result and  a discussion of complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2173301$2662B8B9-5949-4C81-9216-5BF4D3DE55FB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"58309c80337e7309a39fa8b39c69e1b722b3cd2b","datavalue":{"value":{"entity-type":"item","numeric-id":590170,"id":"Q590170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$BB6306C3-388E-4D7E-B71C-6347AE2532B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1bcdc2a107fd2414d151e8610f3471a8784e75bf","datavalue":{"value":"68W01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2173301$16289031-BC84-46D7-BCA6-62B24E1ACCE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2173301$7A9CE384-F054-4EF2-BD3E-9AF50654312D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2173301$E58F524A-927F-4E97-BAD8-494CFB08C218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2173301$5D95C6D4-BBF4-452B-8FF9-96E306E84CE6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e2e7a2642f5e1a50fea426a5b185d13c571007f1","datavalue":{"value":"7191865","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2173301$305A8AC1-A4E5-49F0-AD02-6925D332E6CF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2173301$6E081154-CE85-4985-826D-81FB977DDFE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04c7ddd5496b29877221db84e1264535481f4a3b","datavalue":{"value":"errorless heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2173301$071A6129-FC84-4D62-8A66-5269BF2275E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ceba889d98740fb49fd1ce24a5a27d8aed06604","datavalue":{"value":"paddable language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2173301$1121CFDD-B3B6-4EA0-BCA6-300FBD5CEF44","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":"Q2173301$16757D4B-5D00-490A-8AE7-F95DE41E0A6C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"460028b4bbfc0357f5dc4bac746dcea3ab7917d1","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2020.03.012","type":"string"},"datatype":"url"},"type":"statement","id":"Q2173301$2B9CA9F5-3757-4BDB-BE93-2708760BF5BC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"175e67bf9c4c7ce0c337b48b279ceaa99d134975","datavalue":{"value":"W3012999633","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2173301$0F27CB53-3005-4E18-9DDB-AA16AEC8334B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$46D0D19A-D1E9-49D9-98BD-2B5097DFC6E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$A4407578-BF0D-471B-BCCB-E7E3E2FF3880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4cc4c5b12bdeb4bc8fd4208a2741062bdf868af","datavalue":{"value":{"entity-type":"item","numeric-id":3413362,"id":"Q3413362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$5DE8360B-0837-4F76-A9BE-9D4457E59F0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f878f233476a2906e1851a12c3b560149c275ba","datavalue":{"value":{"entity-type":"item","numeric-id":4780288,"id":"Q4780288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$B6BFFE63-2F3D-47F4-823E-77A09B330A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3963b90870a42a133d18084b017239dcd6378b2","datavalue":{"value":{"entity-type":"item","numeric-id":5645036,"id":"Q5645036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$4045DADC-361D-4C70-BED6-C41BD54A916F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7086dea06f90ad187cd6ca8db29e29ebe9068d0","datavalue":{"value":{"entity-type":"item","numeric-id":4942157,"id":"Q4942157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$A03A9453-16BA-441B-8568-899F1C15BB0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bb8a2afe29f4b6640fda2c29124af0910af9412","datavalue":{"value":{"entity-type":"item","numeric-id":4895818,"id":"Q4895818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$0DF5AC4A-05C2-4455-967A-77F2E8B545D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04533b5e4f54e7a61c4fc1c55a4a47c19e20f43a","datavalue":{"value":{"entity-type":"item","numeric-id":3718151,"id":"Q3718151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$92827753-7E1A-462A-9ADF-CAFD282BBB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"270cf4d4b6cb6dc3f6a450ff5b82876eb78ccf0f","datavalue":{"value":{"entity-type":"item","numeric-id":4790382,"id":"Q4790382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$E8BEB946-7489-41CD-9AD3-EF238AF44345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4b1c731f12bfd44cb2a2bdeeda67137003fa296","datavalue":{"value":{"entity-type":"item","numeric-id":1349712,"id":"Q1349712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2173301$F12DAF4E-8910-40AD-86A7-2C3873D8565B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b1205e05a1977242742c9f101f14cf12ba9c1419","datavalue":{"value":"10.1016/J.TCS.2020.03.012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2173301$D8E58509-A396-4E17-8E4D-015C6B1059A9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47576937d23c61f1e8cee007ff298ff97adab70f","datavalue":{"value":{"entity-type":"item","numeric-id":6073051,"id":"Q6073051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"772706dfc1a350b79f5c0ac3cbb865d12b0a9a0c","datavalue":{"value":{"amount":"+0.7604384422302246","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":"Q2173301$66E78631-A4D0-4875-829D-4ADDADFE2F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a934281aee07300a895d31ed0feef4191a04d6d1","datavalue":{"value":{"entity-type":"item","numeric-id":761039,"id":"Q761039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"631612f6e2c00e7a4f67614d6a0a7bf41bda4aba","datavalue":{"value":{"amount":"+0.6650465130805969","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":"Q2173301$0C3DA266-EC2C-43B2-84A5-F5648FF38612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77b6bf10ed7bea3291bcb0c49d7df7eac5ea392b","datavalue":{"value":{"entity-type":"item","numeric-id":2701740,"id":"Q2701740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5db69c5861026046fb26e7fc67f4ecc09423408c","datavalue":{"value":{"amount":"+0.6637344360351562","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":"Q2173301$656B8936-4F7E-4B41-BA9D-FB40808B30F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dfef4dc959c4897026c29743a9b898ec6273efa","datavalue":{"value":{"entity-type":"item","numeric-id":3680277,"id":"Q3680277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b6bd97bdd35efe35284a4ca7ed69d5412aacec2","datavalue":{"value":{"amount":"+0.6597238183021545","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":"Q2173301$8EB36A2A-71D8-4BB8-9DED-0CD1886859D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7c83e86469b757b6f583c918ac2956f93f071ca","datavalue":{"value":{"entity-type":"item","numeric-id":5900773,"id":"Q5900773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b90b9a3feab5169bd5a1e22f5d12e4725e8eabca","datavalue":{"value":{"amount":"+0.6592966318130493","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":"Q2173301$573A81EE-033B-469C-8ECE-59B5D36A6220","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2173301","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2173301"}}}}}