{"entities":{"Q1192353":{"pageid":1203102,"ns":120,"title":"Item:Q1192353","lastrevid":66819195,"modified":"2026-04-12T13:04:02Z","type":"item","id":"Q1192353","labels":{"en":{"language":"en","value":"Polynomial-time Abelian groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 60754"}},"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":"Q1192353$296751C6-39DE-437A-BAD6-5519E2C05650","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e5fa0da6e0e3a93c50c77a60fa82076e13fda6c0","datavalue":{"value":{"text":"Polynomial-time Abelian groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1192353$FFA0CC2D-A7F0-443B-AA4D-A2BE5F7959CB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4645347433496bc747697e4db1bfa500c91b3e74","datavalue":{"value":"0764.03015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192353$6FC23AFB-DDD7-4352-B1E0-DE379952F6E7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"64b3557ae29bd3538befb04447ed22d458528a49","datavalue":{"value":"10.1016/0168-0072(92)90076-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192353$1E02C1DC-47DE-451D-B6F3-10EB9D5CCD7D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"145c03530c940241521ed95376f4dbe1797e1d36","datavalue":{"value":{"entity-type":"item","numeric-id":524277,"id":"Q524277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$FDD43764-803A-4C82-97C1-029C371364C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5dc30c87ee90e636f091c198a5b55721665c69f9","datavalue":{"value":{"entity-type":"item","numeric-id":698606,"id":"Q698606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$F48316CC-42E9-463A-B2AE-C38DD77FB821","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$8539B833-6E0C-4710-A1D2-F5ABD51AB813","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1192353$B84E8DB6-5912-4A79-9055-B706CE0DF6A9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7f201842cc0c9d838d05e22a40f0b12b5a171530","datavalue":{"value":"The authors continue to study subrecursive presentations of algebraic structures along the lines of their earlier paper [ibid. 54, 17-58 (1991; Zbl 0756.03021)] and that of \\textit{S. Grigorieff} [J. Symb. Logic 55, 260- 276 (1990; Zbl 0708.03015)]. In particular, the authors study the extent to which torsion abelian groups can be presented so that the underlying set and operations are polynomial-time computable. The particular concern of the paper is comparisons and tensions between classical isomorphism types, recursive isomorphism types, and polynomial isomorphism types. For instance, it is shown that any recursive abelian torsion group is recursively isomorphic to a p-time one (Theorem 4.7). Refinements of the notion of presentation such as demanding that the universe is a tally set or \\(\\{0,1\\}^*\\) are analysed. Technically, the key tools are the use of algebraic techniques such as the Ulm sequence, padding type techniques, as well as wait-and-see arguments for the negative results. The results can be seen as a modern ``p-time'' extension of earlier work of \\textit{R. L. Smith} [e.g. Logic Year 1979-80, Lect. Notes Math. 859, 302-311 (1981; Zbl 0488.03024)] and Charlotte Lin on recursive abelian groups, following a tradition going back to Metakides-Nerode, Rabin, Frolich-Shepherdson, van der Waerden, and others.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192353$D8F84A1E-7E48-44B4-BE13-22C617D3F36F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192353$B45EEE4A-87AF-430F-909A-4A769F11ADCF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f83f71ea9a1cf17d1e873f51d3d7d82f401309e2","datavalue":{"value":"60754","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192353$4EA61184-8E07-469E-A23E-8F1F083CA537","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"579fbfd45496bd833bedae77c191974cfb37c11e","datavalue":{"value":"subrecursive presentations of algebraic structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192353$62D379F1-EE4C-4F08-9A7A-7E98FFF96EAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ecd2013fddcf8c60810c14771f88106b1d55a59","datavalue":{"value":"torsion abelian groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192353$B3B40042-10C2-4C5B-9AA6-5BBDEFC1BB3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"733dd9e5fec9e832e1adb326e5cfebd4bafe385f","datavalue":{"value":"isomorphism types","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192353$422199C0-64A4-4541-8322-69AA746562D7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8055ef4c08baf7aae068108b5a3771ed10ad54de","datavalue":{"value":{"entity-type":"item","numeric-id":247180,"id":"Q247180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$7E10BAC1-0A15-41C7-9C5B-3C56F5C5277D","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":"Q1192353$2ADC2273-AA99-447D-8B75-77B235B2B935","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd798b1efb60fd4a7005405734baf47320ce85fe","datavalue":{"value":{"entity-type":"item","numeric-id":1182471,"id":"Q1182471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$E0E215C4-1CB1-475A-9FD8-587E1FA4679A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bee85f15db819554c5cddfac8ba3f64f52efb0bd","datavalue":{"value":{"entity-type":"item","numeric-id":3958432,"id":"Q3958432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$6CEAFE80-B2CA-4CBA-A556-7911537AD86D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adc384805959726b7118d7daa2bf2289bf4524b9","datavalue":{"value":{"entity-type":"item","numeric-id":3489983,"id":"Q3489983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$D03CF78D-09FF-470E-B45A-6CA9478681EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$61E32CC4-A0AE-4432-9519-66217AD525F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6426d070826c71b8b2d2ea6a85844613d9ec3026","datavalue":{"value":{"entity-type":"item","numeric-id":4249727,"id":"Q4249727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$23A0B668-F796-4C4C-B9DF-EB5A96E6AECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"973b025ef5deb72022bf98dad3c19b0781d955be","datavalue":{"value":{"entity-type":"item","numeric-id":5537372,"id":"Q5537372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$1D92A4A0-804E-4F5F-9E2C-B0A3904CD741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfce352d489bf2be4cc44d2364bffb5b41f9f59d","datavalue":{"value":{"entity-type":"item","numeric-id":4035317,"id":"Q4035317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$6B2F6ADB-8587-4C71-99E4-C1CA6C8AD5B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d676e60bcb875cb3e260106d5ae3ee3384116d7a","datavalue":{"value":{"entity-type":"item","numeric-id":3949039,"id":"Q3949039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192353$D62CA88F-8ADF-4DC6-A2DD-65E5C8D1C309","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66f1c42ec50da1e041b4d58519a022ade366fe31","datavalue":{"value":{"entity-type":"item","numeric-id":1182471,"id":"Q1182471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9796701c1755037faf8fbd08b5cb4fca45797c8","datavalue":{"value":{"amount":"+0.8349833488464355","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":"Q1192353$8A3AE531-5654-4068-BDB5-F3CE8FC34279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52813317f753c58dbe3f23f48ee287627c982818","datavalue":{"value":{"entity-type":"item","numeric-id":1816737,"id":"Q1816737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e7fa7f060cb05c0d0b8fb10931f9af3391af9b5","datavalue":{"value":{"amount":"+0.8345754742622375","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":"Q1192353$04408BF3-E85E-4E5C-8379-32C761670C7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7c7d2f451886aaf882ef2e260580ebe3a15befa","datavalue":{"value":{"entity-type":"item","numeric-id":1005925,"id":"Q1005925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5070a2062861d5127055228eca7a307e7d41370a","datavalue":{"value":{"amount":"+0.7743281722068787","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":"Q1192353$96184C85-3DE8-407C-807E-054331E4607B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d119237ffa1b3e98cde07c3c41e715624c54da5","datavalue":{"value":{"entity-type":"item","numeric-id":5457778,"id":"Q5457778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5074a1080db4ddb2f22bfea42ce4f1c16f31e6d4","datavalue":{"value":{"amount":"+0.7652726769447327","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":"Q1192353$BFA3400D-6012-4A0F-9FAB-1F88CDD29244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04f868bb6027651ce0e4817993fc030eb66387a9","datavalue":{"value":{"entity-type":"item","numeric-id":1062753,"id":"Q1062753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bc3409d06791fb16340ff1f1f3ff47315f7ceae","datavalue":{"value":{"amount":"+0.7634645104408264","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":"Q1192353$E2DFCC55-5B9D-475C-8678-0729BE98281C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial-time Abelian groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomial-time_Abelian_groups"}}}}}