{"entities":{"Q960944":{"pageid":962792,"ns":120,"title":"Item:Q960944","lastrevid":50941490,"modified":"2026-01-15T20:49:17Z","type":"item","id":"Q960944","labels":{"en":{"language":"en","value":"The complexity of the weight problem for permutation and matrix groups."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5687572"}},"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":"Q960944$F907CAAC-BA33-4219-BC65-C3C2FA43D122","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cebc9bfa930f1786fbaead1fc09cb852b75a77ce","datavalue":{"value":{"text":"The complexity of the weight problem for permutation and matrix groups.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q960944$66431D38-A8AE-4414-9BCC-8FD35752F968","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e449699ae32c3f115ed151052da70e42328d2cf9","datavalue":{"value":"1211.20002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960944$2AD2BAC9-0DF6-4635-B599-DF22E930129E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6bc2521eae45715fb417b046daabcb23d4401f14","datavalue":{"value":{"entity-type":"item","numeric-id":241258,"id":"Q241258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$F6032B79-2051-4E62-A87A-07050AC573B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee93ba01bffa101c3f82afcd7750a4b9f9858abf","datavalue":{"value":{"entity-type":"item","numeric-id":304455,"id":"Q304455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$234FAAF2-89A2-4188-B130-68F92DD1B6FF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$04087430-E70F-4BFA-A84F-57510C6599FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3e7779b9b8e663f6e735902e827572a0b1b55abb","datavalue":{"value":{"time":"+2010-03-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q960944$6E24FFBC-2D0D-4AC9-ABC8-167317FD7582","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2720e3e144ce31a245cab2ef377ce7e825225132","datavalue":{"value":"Given a metric \\(d\\) on a permutation group \\(G\\), the weight of an element of \\(G\\) is defined as its distance from the identity element. The paper under review is mainly concerned with three problems: the weight problem, the maximum weight problem and the minimum weight problem. These problems are to decide whether there exists an element in \\(G\\) such that its weight equals \\(k\\), is greater than or equal to \\(k\\), is less than or equal to \\(k\\), respectively, for some given value \\(k\\) in the range of \\(d\\).   The main results are that for many well-known metrics such as the Hamming distance, the Cayley distance and \\(l_\\infty\\) all of these problems are \\(\\mathbf{NP}\\)-complete with the exception of the maximum weight problem for \\(l_\\infty\\) which is in \\(\\mathbf P\\). In the proofs, the problems are reduced to problems in coding theory which are known to be \\(\\mathbf{NP}\\)-complete. A similar problem in matrix groups, the eigenvalue-free problem, is also investigated in this paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q960944$597E7224-5018-4E94-942D-69090375D589","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"09c3aba3134af7c9bb8b3553bd325f8ac2e81331","datavalue":{"value":{"entity-type":"item","numeric-id":273070,"id":"Q273070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$1E7AB128-E797-466A-BAE3-5E2496945AAF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"99162f665c9ec138d28e4bea8a477540421995b7","datavalue":{"value":"20B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960944$B94B66B8-7488-427F-9F3B-AC2200C8CAF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960944$DD18FBA9-904B-4812-8AA7-AB367044BE04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960944$59449AD0-BE7A-4CC6-B569-B2C31E0FA3CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960944$61525256-59A8-4285-AB54-B239E47EE0CC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"66bf7d6ad1f8527a4079f5cc64769ec27a4bd669","datavalue":{"value":"5687572","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960944$CE061040-B780-4D0C-AFDF-22C2A428A780","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30c66b655d36c65dc994ac9703534ce11f74cb50","datavalue":{"value":"weight problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q960944$4E34C135-CD07-4817-855F-1929E8FC6A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71eab47e9e07192adf1db12e6be44729d2cc443d","datavalue":{"value":"metrics","type":"string"},"datatype":"string"},"type":"statement","id":"Q960944$44952226-3A48-43B8-9A66-AA1D6E302C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8e3f7e0d18e9c7e5b9f5b19131aa549a1a707c3","datavalue":{"value":"permutation groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q960944$E4E76C2A-DCE4-4955-83FA-E4A0A9F8015B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q960944$9EBB1502-855C-4E1E-81E5-E665A3922A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9aaa5ce1d0c196f05735d43b0c0c1c86ed073c09","datavalue":{"value":"subgroup distances","type":"string"},"datatype":"string"},"type":"statement","id":"Q960944$EF70C336-59D8-4E35-A2A0-5E986C3DCB36","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":"Q960944$292488B8-6E02-4C87-BA50-F53A4E108C57","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a6a6e2949f9644504e6e9fe2b141b481b0c63048","datavalue":{"value":"https://doi.org/10.1016/j.disc.2009.03.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q960944$AE4FA87C-B893-4E9C-BB6C-030036D49849","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"371e943b5e32bee82dd12c138754f05f9b4fb32b","datavalue":{"value":"W2011640602","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960944$149BBA7D-7C30-41F7-887F-152C6F9C5FD8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca29d7d10d8f4dc9ce98d5874bd788d477fa9729","datavalue":{"value":{"entity-type":"item","numeric-id":4156300,"id":"Q4156300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$F6E3FCFC-1E4D-43D0-A00D-C0A328560D91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bb4d63f9302d8162c7b8f6583606b0a28c16c75","datavalue":{"value":{"entity-type":"item","numeric-id":1011736,"id":"Q1011736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$5D28121E-3A4B-43BC-9F2A-3650DC04E95F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cd2a2d4c916d3b4e7158066a8d71896ce859dc4","datavalue":{"value":{"entity-type":"item","numeric-id":1019295,"id":"Q1019295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$B9E333AB-CDEB-45B6-B3A1-38C1857CEFFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fe234b893fe639d56d0ff3a37c6535b70c104f1","datavalue":{"value":{"entity-type":"item","numeric-id":4231664,"id":"Q4231664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$5C519BE4-BEC8-44B9-B6F0-98D4BAC54E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86fd6a9af65cc6377bf4ea4a74dd96f6650cc77e","datavalue":{"value":{"entity-type":"item","numeric-id":1199592,"id":"Q1199592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$8644B29A-AEB7-4DF2-B6EE-97A07110B67D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"265e4ea9c596dfbe68ead41cfa2791c50a3d41dd","datavalue":{"value":{"entity-type":"item","numeric-id":3439572,"id":"Q3439572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$074BC17C-E475-4BA9-9EA6-3D3FBFF9D0BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc97cbc0c14c7607a3b10d8905ec51055ea3a041","datavalue":{"value":{"entity-type":"item","numeric-id":3020034,"id":"Q3020034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$90DEB669-870E-4A1C-906E-8CFE309A03CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"991818938b03de7fb76968560804369e1f92b0ab","datavalue":{"value":{"entity-type":"item","numeric-id":3995195,"id":"Q3995195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$6E4DF423-B22F-4412-8E96-0E163B389971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"126c15e077067f0463ee07748e12e19d5e20e7a8","datavalue":{"value":{"entity-type":"item","numeric-id":3905382,"id":"Q3905382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$32F12FB9-97FB-48AC-8E4F-6CC42CC2FE28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3005a3a58b60a94344b4cdaf143028918063f9a","datavalue":{"value":{"entity-type":"item","numeric-id":4265464,"id":"Q4265464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$A0C9D399-CC3F-4C78-BB69-B54CC310606C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$E06CBD37-63F1-443C-91E0-E5A4F401038D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1981d7289c409add3edb83fea69b28819b573ab8","datavalue":{"value":{"entity-type":"item","numeric-id":3077170,"id":"Q3077170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$710F8B1F-0AD2-4496-984C-5D49A79B0FCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21e55b9b9ccfbf71635f295f65f61bd62be2222a","datavalue":{"value":{"entity-type":"item","numeric-id":1180656,"id":"Q1180656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$66E57D15-FE90-4078-8DD5-068A304A1679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c62ada788f3ca01a4c6f8156af507942db5d91","datavalue":{"value":{"entity-type":"item","numeric-id":4787523,"id":"Q4787523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$5C405772-EEE1-499B-AC9C-5D717ED15DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9058f9ad598ecccc627fc03c87e5fb0bc9e6e573","datavalue":{"value":{"entity-type":"item","numeric-id":4425390,"id":"Q4425390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$7FBF9486-D7B5-4651-8E1F-19957ECD2201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78dc3c6af04e67fcad320e88187d9cc4496d42d4","datavalue":{"value":{"entity-type":"item","numeric-id":4392377,"id":"Q4392377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$305FE4FE-785B-4D45-A4FF-6EF3E57E331F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4036ff68c821883acff7fe514aa217343cd5775","datavalue":{"value":{"entity-type":"item","numeric-id":3140234,"id":"Q3140234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q960944$9CD896E5-5F6D-458B-8DA9-F56A34A57E82","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cbbbd0d1d0b540bd53f1c23fb680256cb353e270","datavalue":{"value":"10.1016/J.DISC.2009.03.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q960944$C1FCCA09-2B72-44D3-AAE3-BB9928F349DB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36a08f75eed675e2a3f3be45e86c08fe8958b874","datavalue":{"value":{"entity-type":"item","numeric-id":3439572,"id":"Q3439572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b9bd003d083ffb13bc86ea97fd5b2b99c3b76e3","datavalue":{"value":{"amount":"+0.9357319474220276","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":"Q960944$F4E0D1B7-FEE4-46D0-8008-B22116FC6F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9b4369304d3f0adab35a7a56eab47777a3d31a6","datavalue":{"value":{"entity-type":"item","numeric-id":5448642,"id":"Q5448642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6de404790217a1d87384d21e60634590fc7b4e7","datavalue":{"value":{"amount":"+0.8697655200958252","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":"Q960944$F6F64A0A-63F6-4DD7-878A-B4133F6428A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"962d46cf7b296c9a4d44b5bdc0e943584dc68ffe","datavalue":{"value":{"entity-type":"item","numeric-id":1011736,"id":"Q1011736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0f2575a8f1df18a40c8a32442e2ae00ef59a590","datavalue":{"value":{"amount":"+0.8260969519615173","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":"Q960944$3DA9D978-515C-4BBF-83C4-C29F02DEDD34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de2abd85cce591eb67fb10813a1b869052d73194","datavalue":{"value":{"entity-type":"item","numeric-id":3077170,"id":"Q3077170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"407123978d3139a7d3aa37d2b7827f3d8275bebc","datavalue":{"value":{"amount":"+0.8114972710609436","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":"Q960944$0642BD6F-08CB-47D1-8354-BA056B7AF09E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d396e518557084a1302ddad03eded4ee3f7cff6","datavalue":{"value":{"entity-type":"item","numeric-id":1019295,"id":"Q1019295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5716cef03f00707e481470ea829c4163afc16847","datavalue":{"value":{"amount":"+0.7570070624351501","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":"Q960944$FF5D80BF-AF58-419A-B5FB-47B82B38346C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:960944","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:960944"}}}}}