{"entities":{"Q1182471":{"pageid":1193220,"ns":120,"title":"Item:Q1182471","lastrevid":66441654,"modified":"2026-04-12T10:05:35Z","type":"item","id":"Q1182471","labels":{"en":{"language":"en","value":"Polynomial-time versus recursive models"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 31341"}},"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":"Q1182471$B13897AE-F91C-4310-82E4-0C79BE0245BD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"536f0752908a24e0b2696a67a08c6b28bc6d53f9","datavalue":{"value":{"text":"Polynomial-time versus recursive models","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1182471$2ECE3ECA-6CFD-4C7E-9687-84CE9AE0DCB3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"de0218497317e03b79837cd200531fa9acf1b853","datavalue":{"value":"0756.03021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182471$6F4FA048-1A72-467E-AB6A-AE535665990A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a13ee82098f2ac63f8fcf9fc776e72d8a01e3b41","datavalue":{"value":"10.1016/0168-0072(91)90008-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182471$966227F9-4A27-4E7D-BE0B-1DF2D592CB30","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":"Q1182471$0F4CBA35-5D54-4B6E-8490-263CD73759F5","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":"Q1182471$BDBDAA28-752F-4C96-B743-85D3CA04EAF3","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":"Q1182471$CF062D28-84FF-44A4-9BF0-89CCF7BDEBA2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1182471$FBEDC88C-6316-44F9-8C8B-0ADB2E42F9A7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7ba4121ce7d9b6182051199382d6e87f56ce12ad","datavalue":{"value":"Roughly speaking, a polynomial-time presented structure is one where the universe is \\(p\\)-time and the relation and function symbols are \\(p\\)-time computable. Clearly there are a number of variations on this theme, for instance we need to consider if the universe is \\(\\Sigma^*\\), or a \\(p\\)- time subset of \\(\\Sigma^*\\), and how \\(\\Sigma^*\\) is coded. These objects were essentially first studied by \\textit{S. Grigorieff} [J. Symb. Logic 55, 260-276 (1990; Zbl 0708.03015)] and \\textit{A. Nerode} and the second author [e.g., Ann. Pure Appl. Logic 44, 71-99 (1989; Zbl 0703.03023)], and are related not only to effective mathematics but to, for instance, online algorithms. As the title suggests, the authors compare the various notions of \\(p\\)-time presentation with the notion of recursive presentation. The main question is whether a given recursive structure is isomorphic to a \\(p\\)-time one. The answer is yes for relational structures, but counterexamples are given for Abelian groups, and for relational structures with universe \\(\\Sigma^*\\) needed. As with the Grigorieff result, the more difficult positive arguments need not only padding but some model theory combined with a priority argument.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182471$74924C80-0D68-4F9B-BFF0-C9898370FEBF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182471$3402833D-B1F7-4170-AF2F-F58DF47EFD1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51c3dc27e13e59ca92a9af5f9c02c332a8b9421a","datavalue":{"value":"03C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182471$D90E044E-FDD2-4B79-8DB8-7B7C53F028E6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6fb3092641776087bb1b61d62d2241d2e6117784","datavalue":{"value":"31341","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182471$58C61ACD-D751-456F-8724-680345AC74BB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"957b0b5bd45c3d743661fbc2af35f515c3382f49","datavalue":{"value":"polynomial-time presented structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182471$72B026ED-7A89-42E1-BB91-3B57CF967369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e8c72166a636aa2ca33b717940a8e68eb5e8e79","datavalue":{"value":"recursive presentation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182471$A8F6025C-E78C-40E6-8C8D-FEBE7CEE2B6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"362b65c58fb7e03db57ecc3fe545b34abd8e9636","datavalue":{"value":"recursive structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182471$346BAEF8-3D71-460E-9D38-D0E1FB690DEB","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":"Q1182471$C5B7C72D-79C8-436C-9CC9-63E778C1D91B","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":"Q1182471$69AC6912-F6FD-45F0-90AE-EB8B309C4C16","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf78011a76fa6fd21c1da295cab54aedc32a84f7","datavalue":{"value":{"entity-type":"item","numeric-id":1225613,"id":"Q1225613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182471$6CBFEA1C-D56A-4EBC-BDA8-5F888FA40078","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":"Q1182471$2B4E222C-3A18-4416-826D-576BAE52992D","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":"Q1182471$87B8EFBC-EAA6-421B-B3F5-EA6C7824271F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8515aeed85af87bd9e0aaeaa4839e0301b65fd69","datavalue":{"value":{"entity-type":"item","numeric-id":915723,"id":"Q915723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182471$A0A7235C-612E-4891-BDCF-3B72AF375D34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8459862735a3ec9272090d344676c06d659741b","datavalue":{"value":{"entity-type":"item","numeric-id":3994998,"id":"Q3994998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182471$1112E612-82CD-4909-8F05-FD43FD3AA1CA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"36b62b2d9c8e727efeb3a4ddafee5f95eec807cb","datavalue":{"value":"https://doi.org/10.1016/0168-0072(91)90008-a","type":"string"},"datatype":"url"},"type":"statement","id":"Q1182471$52134A70-0385-4958-B3CC-CFCEAE214BF5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a1aac9eb5b79501d359d98fc777c739ba54abfd1","datavalue":{"value":"W2056895958","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182471$82E6E1CE-B258-40A2-A315-EA87B0DFDC8D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a431d95db63ade44493d1e3c7c76f1a45114fcf8","datavalue":{"value":{"entity-type":"item","numeric-id":795035,"id":"Q795035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82ddb88cc63b2835dde40212428bff20e3aba5df","datavalue":{"value":{"amount":"+0.88877714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$C69FECD1-BC56-4428-9D48-60D62859551E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a39e745ac0b9e4a0725cdd144f2cd8f29361f86","datavalue":{"value":{"entity-type":"item","numeric-id":5747636,"id":"Q5747636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4946de86836a4f1a2083f0fb5e2122a5b47384c4","datavalue":{"value":{"amount":"+0.8717873","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$A4A1A54A-D276-4940-B174-165F469CE7D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e591bc1a59c20ccf1da66f5fcd8f9cd7c25690ca","datavalue":{"value":{"entity-type":"item","numeric-id":4336699,"id":"Q4336699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f07e31f504f45e8bef463beb3e26e45f403c7987","datavalue":{"value":{"amount":"+0.8697851","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$E12A9B08-BC89-41CB-A8C9-B2D85AF0C918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba1f4be31a170a19cc7a7bd91fd78199368b7b88","datavalue":{"value":{"entity-type":"item","numeric-id":1380428,"id":"Q1380428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1098eb1a62142ea00fdb750e171122667be0e055","datavalue":{"value":{"amount":"+0.8656221","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$FD24B3E2-93C7-4335-A60F-5F493E523E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81c4559f05230f57df55d0391b2fee807801060f","datavalue":{"value":{"entity-type":"item","numeric-id":3476273,"id":"Q3476273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50fb6c80780b3801893d54a65170340ae6aa462a","datavalue":{"value":{"amount":"+0.8627531","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$338F070D-E5D7-4060-AC32-AF2320EC22DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d228c80410229d7aca1b648b226b5b8f81bc5a5f","datavalue":{"value":{"entity-type":"item","numeric-id":3318547,"id":"Q3318547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3662c4b254c8e827c3675cd2d0eb5fdaea45c5bd","datavalue":{"value":{"amount":"+0.85209364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$FB219336-476E-4CED-865C-07ACAED95493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e0010af651dbb739b8f72c2c18444d6e0a37b2c","datavalue":{"value":{"entity-type":"item","numeric-id":4710656,"id":"Q4710656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11a0df9fb419ec72150f80b150b8fcb82c8d6f69","datavalue":{"value":{"amount":"+0.849461","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$1165B032-DFE1-4883-A8B6-42E6F9AA18B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cae79173ee5786c17d2678098fbc30130375d941","datavalue":{"value":{"entity-type":"item","numeric-id":3545596,"id":"Q3545596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f6931cf79e39cdeb98cfdf3c5375243814b98b8","datavalue":{"value":{"amount":"+0.84657085","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$A2E5B66A-B9D3-442B-999C-5A1F65EC6E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fd23dbca0bf4788cb265dc7187b3a747fe1bf37","datavalue":{"value":{"entity-type":"item","numeric-id":4953368,"id":"Q4953368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"961ba131d43d3c1c5b6fa36a358b853088826d76","datavalue":{"value":{"amount":"+0.84569365","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$BAB48B19-C698-48AC-B343-5B9AE208CE62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9ceb8f0a010c986ef683e426a06ce72e211b96d","datavalue":{"value":{"entity-type":"item","numeric-id":3476796,"id":"Q3476796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c1e3fcaf456e21609aa646fc70fcba2a596f78b","datavalue":{"value":{"amount":"+0.8419596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1182471$F4A5CFA9-9A7B-4BCB-B963-6189F8AEB042","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial-time versus recursive models","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomial-time_versus_recursive_models"}}}}}