{"entities":{"Q2221264":{"pageid":2232007,"ns":120,"title":"Item:Q2221264","lastrevid":57793758,"modified":"2026-04-02T13:38:37Z","type":"item","id":"Q2221264","labels":{"en":{"language":"en","value":"The exact query complexity of yes-no permutation mastermind"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7301430"}},"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":"Q2221264$E623897C-1716-4FC7-B15E-CE8654902AD5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"efb8c385aa6a35e959b9e9428b144c09fd6eec4b","datavalue":{"value":{"text":"The exact query complexity of yes-no permutation mastermind","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2221264$B97E79E2-0308-4BE1-931F-6C2ADB6368A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2698b3e3dbefd25084eaa2703eea01c890ac5d8c","datavalue":{"value":"1457.91113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221264$E09867FF-8821-4A0F-B7E3-275394F282A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f952fcf17a335b348550d27b6a02d334f8ab3af5","datavalue":{"value":{"entity-type":"item","numeric-id":247941,"id":"Q247941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$D5AD99AB-827D-4ED8-B97D-6045EB5E0D15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fcbd14c2670550426cf7c5de8c0e48823f5277e6","datavalue":{"value":{"entity-type":"item","numeric-id":1651862,"id":"Q1651862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$083AAD73-DDD7-4D3B-87CD-84A00E25514C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6589dcc6fefca0e1b5c725a60b6e53eec3d18a30","datavalue":{"value":{"entity-type":"item","numeric-id":725005,"id":"Q725005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$57DAB47B-AEC8-4F3F-B4FD-BF59A122D5E8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"00c37197fdcc622dda62b1a70d213b12db611eb0","datavalue":{"value":{"time":"+2021-01-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2221264$208C390C-3A87-404B-8F33-8272D874AFB1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8ece3c55fdd851e5df0a7382829e3b3284779ce","datavalue":{"value":"https://arxiv.org/abs/2003.11538","type":"string"},"datatype":"url"},"type":"statement","id":"Q2221264$8DCAD43F-CDD3-4111-89ED-4BE8967BA29F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3400a418be8a7405ffef907dc6537b7de9f406e","datavalue":{"value":"Summary: Mastermind is famous two-player game. The first player (\\textit{codemaker}) chooses a secret code which the second player (\\textit{codebreaker}) is supposed to crack within a minimum number of code guesses (queries). Therefore, the codemaker's duty is to help the codebreaker by providing a well-defined error measure between the secret code and the guessed code after each query. We consider a variant, called Yes-No AB-Mastermind, where both secret code and queries must be repetition-free and the provided information by the codemaker only indicates if a query contains any correct position at all. For this Mastermind version with \\(n\\) positions and \\(k \\geq n\\) colors and \\(\\ell := k+1-n\\), we prove a lower bound of \\(\\sum_{j=\\ell}^k \\log_2 j\\) and an upper bound of \\(n \\log_2 n + k\\) on the number of queries necessary to break the secret code. For the important case \\(k=n\\), where both secret code and queries represent permutations, our results imply an exact asymptotic complexity of \\(\\Theta (n\\log n)\\) queries.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221264$761692A3-7687-4F77-8475-1B6DBADF9F79","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b62273aea3375cefac54cd8688def5a3b6704b92","datavalue":{"value":"91A46","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221264$8FE83A13-A167-4501-88D9-9BDFB25F4C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221264$6ED1C1D5-7F6C-4911-BAFD-76F5C77A0E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"54aeb167f340633281a9d7b3b52ca287ce6b8d74","datavalue":{"value":"91A68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221264$E9B19C51-95CF-4587-B0FA-D69442898765","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d24a738c31de21ea5336bdb9062a2fc2ca3f57df","datavalue":{"value":"7301430","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221264$1F1939FE-F564-4B8A-927E-31962420D5BA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0de78b729573f576150460387fc204862e45f82","datavalue":{"value":"mastermind","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221264$76805306-E240-43E0-AE6A-39E1F58ED315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221264$4504E5DD-CEE1-49B6-A1EF-A6B7EAEB4143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8745712302d28813999fe70c270cd7743c07054b","datavalue":{"value":"query complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2221264$F0D2F531-E20D-41B0-9109-92D896C32114","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":"Q2221264$582CCA87-2C89-4D2B-9D2C-46F8AD7A1680","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d1a701c5d6127ca834207473afbe9907bf6b0103","datavalue":{"value":"W3016035525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221264$9EEC1480-8595-4AA8-A694-2130037520E7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5e679a3fac96916a90c738ebf1483355a37c135","datavalue":{"value":{"entity-type":"item","numeric-id":4132291,"id":"Q4132291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$A9FD0641-6627-4512-9B69-B4A05943A32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"466396fdcbed1d5344746dbace6973013662e179","datavalue":{"value":{"entity-type":"item","numeric-id":5731202,"id":"Q5731202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$C670E0FF-76F1-475F-A1A0-1699DF7245B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"216064bab0a1984de98d55126f62f78c20c11de2","datavalue":{"value":{"entity-type":"item","numeric-id":753814,"id":"Q753814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$276CAFCC-A485-4174-9D9A-37DE88166001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c4073a706e76acc1c0f75ae3927020de4a35fd6","datavalue":{"value":{"entity-type":"item","numeric-id":989451,"id":"Q989451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$C687A1B7-1240-4EA4-8067-D8717C99B6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd8f16688a38956a0faa326d6cd5497987aa5db5","datavalue":{"value":{"entity-type":"item","numeric-id":1944171,"id":"Q1944171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$8259E092-F131-4F26-8758-AB3B870C6C5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"095b0e559b54f15abeca69691ed6eb56b18d96df","datavalue":{"value":{"entity-type":"item","numeric-id":3768415,"id":"Q3768415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$55097AFB-62C9-4066-899E-F08C6E69B19B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f57b9cf09d672a41ce0dae670b8142eda8f8f36e","datavalue":{"value":{"entity-type":"item","numeric-id":2870055,"id":"Q2870055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$96528847-F9B2-439D-AC56-B8D7A810C55C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef3bc261daa05bfba9f3b0e4e5481aa79659d1a8","datavalue":{"value":{"entity-type":"item","numeric-id":1651863,"id":"Q1651863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$15E2EFC6-3B19-4DB4-AF06-60713895D801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fc99c9f210f959a3122f4bf86de30d24f8129f5","datavalue":{"value":{"entity-type":"item","numeric-id":1690229,"id":"Q1690229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$85D6BC2A-D72C-4354-942F-4304B116609D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a196201910249edb05d515a8ebe6e3622e43681","datavalue":{"value":{"entity-type":"item","numeric-id":1741495,"id":"Q1741495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$429C2F00-5231-4B04-BAF3-0BC8E161AA0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2d181e46d5018542df49513907236b88477db9","datavalue":{"value":{"entity-type":"item","numeric-id":1708631,"id":"Q1708631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$CD16345F-50AD-4AE3-A1F2-4600533132B9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"297b371937846f1130e50eb043cf132d0a1dcaed","datavalue":{"value":"10.3390/G11020019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2221264$F9D71645-7F8F-45C6-A1CC-D61FA5165FA6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fa7c55d893534c8d5154460a204ee07848cc737","datavalue":{"value":{"entity-type":"item","numeric-id":1651863,"id":"Q1651863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"661dc01c766079e45f336c1545bddbe1e1c28e5c","datavalue":{"value":{"amount":"+0.8633788228034973","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":"Q2221264$716D6ED6-316E-4611-AD29-1906CDFE75D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c825ac22e08a5904ade826d4dfd06fa1f5a2871","datavalue":{"value":{"entity-type":"item","numeric-id":1690229,"id":"Q1690229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00bc54e080f8e0eb152709ab15cee5f7f8db4134","datavalue":{"value":{"amount":"+0.8537590503692627","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":"Q2221264$5BC6D9E3-34D5-4E5A-BD63-9BAC40D8FFA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37e6cab1448de8e8f89a284c2f66c56002cd6bd6","datavalue":{"value":{"entity-type":"item","numeric-id":2222951,"id":"Q2222951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9265f36086d55f25cda128ff406a5ed6e8406e52","datavalue":{"value":{"amount":"+0.8491742014884949","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":"Q2221264$B5737973-0089-44DA-98BE-0388F27F534F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9779ce56853883d162d7a53d14fcd184a4f625a3","datavalue":{"value":{"entity-type":"item","numeric-id":1741495,"id":"Q1741495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7368aeae7fb74f935da3e6a11d5d99eeabaa5618","datavalue":{"value":{"amount":"+0.8418858647346497","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":"Q2221264$A34D4740-D975-424A-9910-747CD1A38C3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66f27d3b5d144547ff4e97763318e6b018a50e09","datavalue":{"value":{"entity-type":"item","numeric-id":2073315,"id":"Q2073315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d88d899ac1f60249cd117cab4fc6d5ab449b0a80","datavalue":{"value":{"amount":"+0.8351045250892639","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":"Q2221264$F8A28AF1-D708-4210-B736-24112F8D3C62","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2221264$37FF3B6A-A543-4301-BD95-F14C0E882181","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2221264","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2221264"}}}}}