{"entities":{"Q6995148":{"pageid":21473880,"ns":120,"title":"Item:Q6995148","lastrevid":83874140,"modified":"2026-05-07T13:10:32Z","type":"item","id":"Q6995148","labels":{"en":{"language":"en","value":"Membership problems in finite groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8029243"}},"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":"Q6995148$EADA186F-2907-4E28-B650-0BFF8D5B423A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"79773c5ca33409182917f5429543f22dc501e37f","datavalue":{"value":{"text":"Membership problems in finite groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6995148$FC67C294-55DC-426C-AA7E-593A8B28B805","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"91de68a782a7aa033d2085a5899e54ad5b71b7ee","datavalue":{"value":"1562.20034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6995148$B699865C-0AE8-49E7-94FD-1D76B786B249","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"66b0b711b1ed1da651d8cbb5983c6d79551fa66f","datavalue":{"value":"10.1016/J.JALGEBRA.2025.03.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6995148$970486D2-8432-41CA-927A-710AAA8D58EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db8f30a521e20eb0f40199bc337d407bb71223c1","datavalue":{"value":{"entity-type":"item","numeric-id":269346,"id":"Q269346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$EB7F67D3-1B37-4213-8723-CDF632609208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ce15dc8e235499a14987fcc7e61db0f3d763cbf","datavalue":{"value":{"entity-type":"item","numeric-id":2156373,"id":"Q2156373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$0B9D0342-5C84-477B-841C-B517778CF17D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a981040b7cfe2c1a3a7b860b2700c236f2b8a237","datavalue":{"value":{"entity-type":"item","numeric-id":1675162,"id":"Q1675162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$5B42EC6A-12FD-402A-A188-4D2AE20F5F20","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"93541bb195a0809b1f249396bcebe99d047e6b6c","datavalue":{"value":{"entity-type":"item","numeric-id":161561,"id":"Q161561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$21DE754F-53DF-4890-B9CB-CEA7401B5A4B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7f94f0c0a2717ce4f40eea9c072fbe52c006e4c4","datavalue":{"value":{"time":"+2025-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":"Q6995148$1E747364-DE6B-4262-AE0A-4ED953812DDE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21e145db4e77158e17e08708eb987f2012eda459","datavalue":{"value":"The authors investigate several classical and new membership problems in finite groups, focusing mainly on permutation groups. They prove that the subset sum problem, the knapsack problem and the rational subset membership problem are all \\textsf{NP}-complete in symmetric groups \\(S_m\\), sharpening a result of \\textit{E. M. Luks} [DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 11, 139--175 (1993; Zbl 0813.20004)] by showing that \\textsf{NP}-completeness already holds for products of three cyclic permutation groups.\\N\\NThey further study the context-free membership problem in permutation groups, proving that it is \\textsf{PSPACE}-complete in general but \\textsf{NP}-complete when restricted to grammars of bounded Horton-Strahler number. Their upper bounds are established even in the black-box model of group computation. Applications are given to intersection non-emptiness problems for group \\textsf{DFA}s (finite automata with group-labeled transitions) and a single context-free grammar, improving known complexity bounds.\\N\\NAmong other contributions, they show that membership in products like \\(\\langle g \\rangle \\langle h_1, h_2, h_3 \\rangle \\langle g \\rangle\\) is \\textsf{NP}-complete when the \\(h_i\\) commute, refining the structure analyzed by Luks [loc. cit.]. Various new hardness results are obtained both for subset sum and for knapsack in symmetric groups, even under abelian restrictions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6995148$C9B8BF0E-D495-4F42-9C5E-676AA075BCFC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5bfd82087b720927b1a296c318191d7cfc2aac2e","datavalue":{"value":{"entity-type":"item","numeric-id":284097,"id":"Q284097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$B05B2FBF-EAD0-4CCE-8ECA-2F419B0BB7BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6995148$D4CFB079-DF0A-4557-9546-2F5FD04394FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"40a17c7590d207693a91f511a74f778bb78de167","datavalue":{"value":"20B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6995148$4020860C-E3ED-419D-AEE6-0D8838070D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6995148$53FDD985-6998-4C64-BCA2-4B7D7360EFCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6995148$8EB0ECF0-9419-47A0-B18F-77C6699869DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6995148$E1509496-D0B1-48C9-96D5-E61C92490D55","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3cc9a89d539281048be239a3a1ace088a4a3885","datavalue":{"value":"8029243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6995148$C97AA4B5-665D-40B6-9058-80FE42E0D08E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d45a52e2642bb7f2aa21f16dfda8a495c756b6d3","datavalue":{"value":"algorithmic group theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q6995148$6E23D8FC-56AC-439F-B386-F4CFBEA2B33B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a2a5aaf2813613e191091bab6a7937bd2f6db3d","datavalue":{"value":"membership problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6995148$45014E6F-6C7E-4773-BA6D-3B5EF7A648F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68c261570392928413cb911f93665f42e10898b6","datavalue":{"value":"automata theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q6995148$CD3053B8-FBDB-4356-8D07-BDC51DFF7A96","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":"Q6995148$336A1F78-4F30-4A22-851F-09577A6C661B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d8653d2e6f53b17cedec7b9470bcf88609d4f1f","datavalue":{"value":{"entity-type":"item","numeric-id":5320667,"id":"Q5320667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$ED94E666-40C9-4B6D-B2C7-6AB09A59BF19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0403a9082769063ec294cb9fd28b54c16c493fd","datavalue":{"value":{"entity-type":"item","numeric-id":6187048,"id":"Q6187048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$0AD71007-D9D3-4CC2-BC0E-BDEF9D1E98AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c80ff9b6aba9b771609ee53cd6aed17b5740d2e","datavalue":{"value":{"entity-type":"item","numeric-id":5361871,"id":"Q5361871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$4448EFE7-7544-49F4-83B1-151EFC656607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91e296852d5ecd78dd72b2d7fbb6d4a0be02b255","datavalue":{"value":{"entity-type":"item","numeric-id":4875224,"id":"Q4875224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$2EB40B8D-06AD-4C7D-8CB8-AAF00C4A8BC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9748793198cfdb8d04eab0a1c4b7562b6f52ca4a","datavalue":{"value":{"entity-type":"item","numeric-id":3601323,"id":"Q3601323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$6C7BA9BD-C85F-40AE-8B96-3494E3D0628A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4743d8545e31e5374c6f8da972c29d51e6a90417","datavalue":{"value":{"entity-type":"item","numeric-id":1575552,"id":"Q1575552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$EE57C190-F275-4514-8DC3-A12DFC513F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92bf1485810a300ea994e9295c3f39a0174a10c9","datavalue":{"value":{"entity-type":"item","numeric-id":347114,"id":"Q347114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$C745C037-4A76-476D-A70C-4619DEE52243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9285a61f3039e7ce640456a9ea2b4d13665dc77","datavalue":{"value":{"entity-type":"item","numeric-id":5626625,"id":"Q5626625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$05DE3CFF-A118-436F-9AC8-915A1DF1C477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9899ac0109fd642fd66a40841606da613f5985a2","datavalue":{"value":{"entity-type":"item","numeric-id":5041250,"id":"Q5041250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$8F8CDD53-13FE-4355-8EE3-87BF35F6B1E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e902457964a312a605389238232d33897eb4c84c","datavalue":{"value":{"entity-type":"item","numeric-id":1887158,"id":"Q1887158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$D3DAE10E-CE0C-4B75-B503-5B447AD72D1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdfb6f4c3cb2a513720d0512ac6ad9a80b12c309","datavalue":{"value":{"entity-type":"item","numeric-id":5404898,"id":"Q5404898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$34CC20F0-E263-49D0-829D-BA7BBDBA20FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f949f13e1712b62b2dca0010c2a3997b4691a24a","datavalue":{"value":{"entity-type":"item","numeric-id":3920644,"id":"Q3920644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$48DC5493-E5CB-4C61-94C6-2318DB520C6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b276f9d383d60aaffb537b299c98658c2d8cbefc","datavalue":{"value":{"entity-type":"item","numeric-id":6842444,"id":"Q6842444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$D268CFB9-8ECC-4364-96C9-F8B11C3F0F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"644d65ea318d4c33ab5ccc0194560db853a13a72","datavalue":{"value":{"entity-type":"item","numeric-id":898247,"id":"Q898247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$0C2EDAEF-561D-415F-8727-C4A42A36B7F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$C622A584-62C9-46EC-8F4A-100941018737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9c64760b3ff8e001c456c7036ce734ff8500bb6","datavalue":{"value":{"entity-type":"item","numeric-id":5900852,"id":"Q5900852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$6A89A026-5A83-45EA-BCC5-01539F291FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$47AEC9C5-610C-4F15-9325-1A6744AF9176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d2861068ce2dce5975bcacf1aa90b84a22e43b7","datavalue":{"value":{"entity-type":"item","numeric-id":1058290,"id":"Q1058290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$81B6BFC0-B51B-4C26-ABB0-7C268870D798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca6acd337dda8a73d0fdbfa20b23945c1a8a8a0c","datavalue":{"value":{"entity-type":"item","numeric-id":875109,"id":"Q875109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$39019654-CFA6-499B-A80C-757B246AC5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3237417c2bdb1dad38edfdf0e35161d25a71fac1","datavalue":{"value":{"entity-type":"item","numeric-id":1599084,"id":"Q1599084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$51023C06-4F87-4FCD-B219-1E2CDDD5BFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9bba9ab59906e8999a373417219bc31e7b36287","datavalue":{"value":{"entity-type":"item","numeric-id":2685503,"id":"Q2685503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$4004D8A2-2994-4CA4-9086-5FB12DFAEFC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc72a981ad05ab708bc5da0be598bcbe23ed2188","datavalue":{"value":{"entity-type":"item","numeric-id":2975251,"id":"Q2975251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$392E2F6D-2B24-4700-9EBD-4CD8E710D87A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26d5501a6de5a1aad7a0f94a592e6c992dc4f008","datavalue":{"value":{"entity-type":"item","numeric-id":2990055,"id":"Q2990055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$88D3D4E8-CAC4-4073-A6EA-E18161D91157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b54ba3c92f0b8d5244001ec3fd5403f2d56fa1d","datavalue":{"value":{"entity-type":"item","numeric-id":5919299,"id":"Q5919299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$43F3E387-E149-4ED1-A29B-ECC86FAF012F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"456f0891667b4ca2590ed04ab0a5fea5f3755c67","datavalue":{"value":{"entity-type":"item","numeric-id":6584075,"id":"Q6584075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$CA9F1095-4635-4887-891B-D68B09AF4D99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"525e2acf1881cf77939b828f04e984c379070b9e","datavalue":{"value":{"entity-type":"item","numeric-id":1702854,"id":"Q1702854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$846C1BB0-9854-4A8B-8237-BC3C94A86169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2de3ec857f6169c81f2908b5b9720efbe3cb44f0","datavalue":{"value":{"entity-type":"item","numeric-id":1168744,"id":"Q1168744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$9FCFF5EA-F898-4517-AE40-FB3018B95B36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"067e393b8b4356a444ebb86fe4868b077a480748","datavalue":{"value":{"entity-type":"item","numeric-id":4273608,"id":"Q4273608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$93B2B74C-18EA-4EC9-89F2-99740ABFF326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a54395a90759bc40021d64620686ae3bf0c4d5f4","datavalue":{"value":{"entity-type":"item","numeric-id":5496223,"id":"Q5496223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$7A652FDA-1371-4FD0-A0B9-C14248B3E7DA","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":"Q6995148$704BAF95-8D61-41EB-9E70-5F479FECAF56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d545d46281c27f7c22d936768292713b57021712","datavalue":{"value":{"entity-type":"item","numeric-id":5617749,"id":"Q5617749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$B6171178-D895-437F-9F16-76E7E593BCB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3cad63c818dc1a3a4c509e9f28c0b60156a5876","datavalue":{"value":{"entity-type":"item","numeric-id":3449493,"id":"Q3449493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6995148$956F0F59-1910-4AE2-AD51-73BCBF04A7AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Membership problems in finite groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Membership_problems_in_finite_groups"}}}}}