{"entities":{"Q581532":{"pageid":583299,"ns":120,"title":"Item:Q581532","lastrevid":62941653,"modified":"2026-04-11T09:07:26Z","type":"item","id":"Q581532","labels":{"en":{"language":"en","value":"Computing the composition factors of a permutation group in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4019303"}},"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":"Q581532$BACE27AA-9EC0-473A-BA65-821E0846B3FB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dfaade6cad664ecd7cfca7ebc8dbe6dfcfd74df8","datavalue":{"value":{"text":"Computing the composition factors of a permutation group in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q581532$DE74F153-F992-44DE-AF17-4B8C23BCDBB0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7fd05d41db82fb604c703d545be542ff02d2c94","datavalue":{"value":"0627.20002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$49516614-B566-43A5-8777-8EA6A30975E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d1461b05efb187cfe7d3cd5c86818fa6b283255","datavalue":{"value":"10.1007/BF02579204","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$96D82468-0536-44C4-A417-A669FBD680E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$CCA89136-E50D-48F0-BCD5-31BCD521B5B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q581532$591C10EE-82FB-40D6-AF5C-6721D2FFEF3D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4487839dfb215e4b3eb4915a054bfe6674b5dfde","datavalue":{"value":"The paper gives a proof that the composition factors of a permutation group G of degree n can be computed from a given set of generators in time polynomial in n, a result that had previously been announced and sketched by the author [\\textit{E. M. Luks}, J. Comput. Syst. Sci. 25, 42-65 (1982; Zbl 0493.68064); \\textit{L. Babai}, \\textit{W. M. Kantor}, \\textit{E. M. Luks}, Computational complexity and the classification of finite simple groups, Proc. 24th IEEE Symp. Found. Comput. Sci., 162-171 (1983)]. As this author states explicitly, he restricts attention to the issue of polynomial time without disgressing to optimize the time bounds. So also the question, for which size of groups the algorithm lends itself to practical implementation and use is left undiscussed. This (in the reviewer's view) more important question has however meanwhile (a first draft of the paper under review was received 1981, the final version 1986) been the topic of several independent investigations, see in particular \\textit{P. M. Neumann} [Groups, Proc. St. Andrews 1985, Lond. Math. Soc. Lect. Note Ser. 121, 59-92 (1986; Zbl 0612.20001)]. The present paper states briefly all needed prerequisites with careful references, as all these approaches it builds on the O'Nan-Scott classification of primitive permutation groups.","type":"string"},"datatype":"string"},"type":"statement","id":"Q581532$6B68C5C0-802B-4A47-9BFE-6D693EF78CA8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"40a17c7590d207693a91f511a74f778bb78de167","datavalue":{"value":"20B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$B63EE456-95CB-4634-BE25-2AA601DBE185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f96720fe29e309c34c82deec20bd95823bb71652","datavalue":{"value":"20-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$2CFF9AAB-703D-4B06-848B-70AA28234390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"99162f665c9ec138d28e4bea8a477540421995b7","datavalue":{"value":"20B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$08AA6F75-9D33-4316-A52D-CBA471B31255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$B6E23B72-AA00-48D2-8806-7718C7707158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3367018dbe2ad5da0826b32cb1ef14710133d281","datavalue":{"value":"20B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$CBEBFDC3-6FCB-4D38-A6FF-58C0936DDDE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f7e20e8cedacec1d370ef046cc110b16c0d5386","datavalue":{"value":"20D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$F20684BC-02D9-4000-809B-843B4AEBD13B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"11692afa6523176536de4d892883ddccdf8d2601","datavalue":{"value":"4019303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581532$30B1DA0A-F785-4E17-BF0E-D151A93E35B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d85c121e6e6200a1d4667137fca957de2656737","datavalue":{"value":"polynomial time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q581532$D4D7E312-214C-45B4-8E06-4F96C96491B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4780b02cfc7bc35a586062e3271a9f52fa94f067","datavalue":{"value":"complexity analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q581532$3F78C7E3-F86A-435B-9E1C-5E2B279233BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71aaa81d4d4fb4aa2346655125710b75c3af1be2","datavalue":{"value":"composition factors","type":"string"},"datatype":"string"},"type":"statement","id":"Q581532$8F5C4516-E471-4864-B053-824FDFCBF890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07f85129e5a74252a21c1c1a16f98e8c7008066e","datavalue":{"value":"permutation group","type":"string"},"datatype":"string"},"type":"statement","id":"Q581532$BCD8E9A4-5E5E-45D3-BFEC-CCCCFCB2B4CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc17530683f05aacef7e862f12bdb2dce0ac1ceb","datavalue":{"value":"generators","type":"string"},"datatype":"string"},"type":"statement","id":"Q581532$A8CCEEA9-8DA5-47DE-A6B3-5F4DC1E0B19D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"901a9df279aa2ad41eaee88407011e6ef2970601","datavalue":{"value":"primitive permutation groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q581532$2FA7E40F-322D-43FE-9ECF-483622067565","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebfe69d7798450ed18733ee399dbc5d2aa63e020","datavalue":{"value":{"entity-type":"item","numeric-id":959772,"id":"Q959772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$A38B3FB2-CCAE-4713-84AC-67CD8FA18498","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"837f1ed5523453fc24787bd0297b3654f5e5939e","datavalue":{"value":{"entity-type":"item","numeric-id":755889,"id":"Q755889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$37C39A9A-61D4-41D0-8B0E-6B4089C30ED9","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":"Q581532$9CA57C01-0235-4351-84E6-66847B0D8D0F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$CC30E770-94BF-4165-813D-626612B576AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83969f6d3b28492352194d15fb4d49ca427d7e98","datavalue":{"value":{"entity-type":"item","numeric-id":4068903,"id":"Q4068903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$7B98A9AB-BC04-4A49-99DC-073AC487A965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89114344afb55319f83e26b6ed19450dcb689a11","datavalue":{"value":{"entity-type":"item","numeric-id":3913570,"id":"Q3913570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$0415586C-56A2-4583-986A-75247F949E75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b2299511bdd9257e24d50dbcbe6126abc656159","datavalue":{"value":{"entity-type":"item","numeric-id":2393741,"id":"Q2393741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$BBF71053-3ADD-4206-91F8-DD842F52F1E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eadf437b7ee30e99c93ca5ecc9d61f0d1e67396","datavalue":{"value":{"entity-type":"item","numeric-id":3912839,"id":"Q3912839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$6D174229-9CC8-4801-BE0E-63C3BCADDB18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52efde1880fc5b135035c62c4d5cfa1c513c3787","datavalue":{"value":{"entity-type":"item","numeric-id":1063109,"id":"Q1063109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$B33C3BF8-DD56-47C5-925C-E9A4790119FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfc21bf3b5e9c96b000a4517c17232ccb0119b44","datavalue":{"value":{"entity-type":"item","numeric-id":3741775,"id":"Q3741775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$76A64AAC-2E5B-4F1B-81F0-9E913F7EDFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f9ebfe530300e830e0ff89de4989f1ac74c0f9","datavalue":{"value":{"entity-type":"item","numeric-id":3784308,"id":"Q3784308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581532$9993C01E-7288-4ECF-A519-E316E7E8554D","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":"Q581532$1E3B98BD-3C84-4A7B-81FE-893DD7FDEB53","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":"Q581532$7E2019A1-9BBE-4FE6-9734-DED09BAC2B74","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1760d4e04898575ecb0227979834c4a245c779b","datavalue":{"value":{"entity-type":"item","numeric-id":4234185,"id":"Q4234185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9d2f81218fcdbc0d0099c2eda7475fecebaeacf","datavalue":{"value":{"amount":"+0.9101956486701964","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":"Q581532$6BB3A1F9-D0C9-488C-8B77-B46BCDCBCEB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227c89bb957aaf516a74fb9bcfb2cee9e75c9ada","datavalue":{"value":{"entity-type":"item","numeric-id":4020769,"id":"Q4020769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9d2f81218fcdbc0d0099c2eda7475fecebaeacf","datavalue":{"value":{"amount":"+0.9101956486701964","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":"Q581532$BA608258-64EB-4430-8F68-35FF5A3ADDEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bff25d672ea3029633e0ca5dc410ed0f59a9e816","datavalue":{"value":{"entity-type":"item","numeric-id":4273598,"id":"Q4273598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b157d09ed72ecac5c7d29fd5bf9d16747f01f0f","datavalue":{"value":{"amount":"+0.8971706032752991","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":"Q581532$C970E7EF-56E5-40B9-8CAB-E2FE952913EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f8ca36e6759cda1b53f024b18ec6f36f27cdd97","datavalue":{"value":{"entity-type":"item","numeric-id":3784308,"id":"Q3784308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66a76dd98f2108cb680fd99f92db8ba9186702ac","datavalue":{"value":{"amount":"+0.894182026386261","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":"Q581532$AEB5790F-B6D6-442B-807A-582DCBFB1A48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f3093cbd41eee3958f9f1acf4748dcb9c70d6c5","datavalue":{"value":{"entity-type":"item","numeric-id":3752563,"id":"Q3752563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02d7305d55b7bf48f008bbc77f04846e6ecd6417","datavalue":{"value":{"amount":"+0.8645278215408325","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":"Q581532$7E26FDCD-982E-4459-9105-836308F31280","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing the composition factors of a permutation group in polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_the_composition_factors_of_a_permutation_group_in_polynomial_time"}}}}}