{"entities":{"Q4457727":{"pageid":6487326,"ns":120,"title":"Item:Q4457727","lastrevid":109324394,"modified":"2026-11-12T02:40:28Z","type":"item","id":"Q4457727","labels":{"en":{"language":"en","value":"Strong extension axioms and Shelah's zero-one law for choiceless polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2061947"}},"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":"Q4457727$B37EA1B7-A279-4EC6-B696-11B39EDE8245","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1641de73af78e06e6a051737fd229d385066097a","datavalue":{"value":{"text":"Strong extension axioms and Shelah's zero-one law for choiceless polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4457727$3D440305-4760-41D4-AE1E-006D432A6EE9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7458fe19412e42124afa6aad5082def93892ee3a","datavalue":{"value":"1045.03039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$AAEDF65B-4EA1-4E44-9557-2C802D46E24E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be0c547959f56e22bcdd079e76bda78b5f7c3224","datavalue":{"value":{"entity-type":"item","numeric-id":195660,"id":"Q195660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$8FA7F748-CBAD-4B96-AC42-2B4C491FDA74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aee4d3ee1c41565a5a83b17f16adc6668f5bedeb","datavalue":{"value":{"entity-type":"item","numeric-id":293302,"id":"Q293302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$F50B47CF-79B9-4B93-A9A3-3C5CA415FFE7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6218d42f0175ef35f91c4900eb5db86484a9463d","datavalue":{"value":{"entity-type":"item","numeric-id":2710590,"id":"Q2710590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$E8569D7E-CB29-4225-862F-644CDD5128B4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"389b767007343732466af50d3ede33c114d8b0f3","datavalue":{"value":{"time":"+2004-03-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4457727$E7D11201-8C69-4540-9658-F7B1BA25EFDF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$39F0851B-1A66-4FC6-8DDF-8EAF87D3C6D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$50B86D94-00F1-4196-8A89-30CD3827D079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$3C54AE90-E6B7-4114-AD48-DA071E95411F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$D0D592FA-0B80-4DAB-94C0-F43E64888001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$22CC966B-AD7C-4D2A-A741-2A6D6E50E963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$EA941BEC-36D0-4648-AAB6-92D6B4FBD679","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4e3eee10c46f70bfff3ecac8e696827a7e5a71e2","datavalue":{"value":"2061947","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$2864DCEB-CFAA-40BA-AC4B-76E90755B74C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e864cffb193b7ac093ea58ec700eabb03ada4c2","datavalue":{"value":"extension axioms","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$B5FD51B8-5CC8-495C-81D3-DFE53CF70FC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8c306ac5bbf5cf358785eec041285b1cb8d24de","datavalue":{"value":"zero-one laws","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$2791C365-A6F5-4EBA-AE3E-A19E7B762A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0af597ed982aa4975f0f0e535f36cd921fd1206","datavalue":{"value":"choiceless polynomial time machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$CC05A990-75B4-4AC0-AA4F-D33A46180CCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a0d8ae99437d8f499a2e4fb2392891663090b37","datavalue":{"value":"choiceless polynomial space","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$4439EA0C-08C8-4CC5-B0E3-D15274E34B8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac0b57124f778a7e54eb92971b7aabc1dbd2f48a","datavalue":{"value":"constant time computable","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$75AE1CB8-71D4-485E-91DF-D9DBC7E15AFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$1C997578-9112-4117-A71F-462681D09311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3eb75a01542f73e3891235a91585b74ccf416dcc","datavalue":{"value":"random structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$6D14F9E4-0071-4476-BE1A-694844798080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"810a316a495151b393a4a1b38601c26a3807bf6e","datavalue":{"value":"random signa","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$067F3DB4-4BEB-4BDE-82A1-22F35876BC48","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":"Q4457727$29C02F94-C551-4728-A496-87BA6DEA00C6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd3f2b258997f84f00c38411fced9ca80b114b1d","datavalue":{"value":"https://doi.org/10.2178/jsl/1045861507","type":"string"},"datatype":"url"},"type":"statement","id":"Q4457727$3996F8E0-1FDB-466F-A2C7-20DA0D5A5262","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5342800e3b309e317e69cf268a4a5b14910fcdcf","datavalue":{"value":"W2116445981","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$014B1467-D5B8-4E38-BCBB-EA52D6213F4D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dadd920105fd2dc8c3c88d08d58848760b22122","datavalue":{"value":{"entity-type":"item","numeric-id":1125059,"id":"Q1125059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$79C2535B-C849-49EC-BFBC-B832CF85E9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8099d51f8a881efdd415b36f40b082090e800446","datavalue":{"value":{"entity-type":"item","numeric-id":3208703,"id":"Q3208703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$ECD66CE2-1AA6-4829-8C7E-84474583A7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b051bb91a42a31736fdd8d09157004cdcec793d8","datavalue":{"value":{"entity-type":"item","numeric-id":920075,"id":"Q920075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$11F053DC-42D5-41ED-9C9A-F94B955286FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f3e217d975577abd60153ec008522cd4114ebdc","datavalue":{"value":{"entity-type":"item","numeric-id":2711918,"id":"Q2711918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$D582D975-3589-44AD-B1D0-15DF3781C9C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$7E294796-C766-432C-95D2-72D20C716ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bb13266d6e9cb924de9f33fbd05c2696a4d4948","datavalue":{"value":{"entity-type":"item","numeric-id":3747760,"id":"Q3747760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4457727$EB2E0794-4C18-4B94-A691-152EA6F9D70C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"397c0db80aa7b6cbea39279c28b7fba5f6cca849","datavalue":{"value":"10.2178/JSL/1045861507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4457727$1833015F-73E7-4308-976D-FB731CAFF714","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7325a616212d4161e0cfa8aa555bdbd3dbebeaab","datavalue":{"value":{"entity-type":"item","numeric-id":6109071,"id":"Q6109071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7f0f8f112f7afcf2eafae2e9b480f4059ce0fc5","datavalue":{"value":{"amount":"+0.8945501","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":"Q4457727$79540D7B-37F9-4BA4-B6AB-46507FF06DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84ac6ad2faacb5da9c3bc98357e4f28cf3038c4f","datavalue":{"value":{"entity-type":"item","numeric-id":2753664,"id":"Q2753664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"182e97113fbf1645f5daa319e26fc6ac1607a3f4","datavalue":{"value":{"amount":"+0.88799447","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":"Q4457727$41A54E98-0992-4AD5-B8C7-BA2C633856C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41edc5a236d1b7a28cbd6c5831bcacc0892bb515","datavalue":{"value":{"entity-type":"item","numeric-id":2800573,"id":"Q2800573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2647e1415014b28838b53b02e3868513d115e1f5","datavalue":{"value":{"amount":"+0.86003673","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":"Q4457727$8C1A6D35-7707-4343-A704-92620A0835BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea0dbfbafbd661af73bfff2ecc3633a38f5a45b0","datavalue":{"value":{"entity-type":"item","numeric-id":5945399,"id":"Q5945399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59945e63a9c2ecf31fcac0de394cf134f1179bed","datavalue":{"value":{"amount":"+0.85842746","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":"Q4457727$8A053328-A524-41D6-B1BB-03D5C6C1CFC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23f69dd7b2a164cbee70da24e4af4d228718a09b","datavalue":{"value":{"entity-type":"item","numeric-id":2710601,"id":"Q2710601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"862566cf608c812e2dcaa8eee7dae66971e895c2","datavalue":{"value":{"amount":"+0.85766643","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":"Q4457727$257DA5DA-E80D-4827-855E-1B0C89B6743A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ed7a1490ccdbe1b7f0860f8ab75fec6948cded9","datavalue":{"value":{"entity-type":"item","numeric-id":3644737,"id":"Q3644737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c1628fdec0df6498855323953f413b337326aa0","datavalue":{"value":{"amount":"+0.8554387","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":"Q4457727$C26AB167-4297-4501-82C0-AE12BCA02FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8e85e69c97abfeb1a1b7ede13608a12658b9b4a","datavalue":{"value":{"entity-type":"item","numeric-id":4733404,"id":"Q4733404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5b5fd0649868bd6886ff2a393ce82753b6862c0","datavalue":{"value":{"amount":"+0.85472894","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":"Q4457727$969F843C-71F6-489C-9E9F-9F5AE8D59F31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3df76b7de088bbb19e04a1927fbfe0ac58d6e88f","datavalue":{"value":{"entity-type":"item","numeric-id":2729229,"id":"Q2729229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"605eea8f3618e90aa93fd6d873f8c0ce8e463bd9","datavalue":{"value":{"amount":"+0.8541291","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":"Q4457727$D28F6D18-0C8B-42B0-B89A-CAAC6A841CD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc78d969c23e46b2cc5a4f7225bbac14701c3ee2","datavalue":{"value":{"entity-type":"item","numeric-id":4665729,"id":"Q4665729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"605eea8f3618e90aa93fd6d873f8c0ce8e463bd9","datavalue":{"value":{"amount":"+0.8541291","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":"Q4457727$6E2ACD75-4D4B-4537-A210-18364DF3175C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cb854b5a40d01e83289e18b8f6389aeeeb6d542","datavalue":{"value":{"entity-type":"item","numeric-id":3974876,"id":"Q3974876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1823124e3d1e4e46521092accc08a0b2e98e4995","datavalue":{"value":{"amount":"+0.85388505","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":"Q4457727$D764F44A-1BC6-4701-A944-D1654CFE16DB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"59b37bd75d32fc1c3973c0c0f1f0a5219b5b399a","datavalue":{"value":"This article explores the stochastic behavior of the choiceless polynomial time machine (or BGS model of computation) introduced by \\textit{A. Blass}, \\textit{Y. Gurevich} and \\textit{S. Shelah} [Ann. Pure Appl. Logic 100, 141--187 (1999; Zbl 0936.03037)]. Much of the article is devoted to an exposition of a result of Shelah [\\textit{S. Shelah}, ``Choiceless polynomial time logic: inability to express'', Lect. Notes Comput. Sci. 1862, 72--125 (2000; Zbl 0973.03055)]: if there is a BGS program \\(\\Pi\\) and two classes of structures \\(\\mathcal K_0\\) and \\(\\mathcal K_1\\) such that: (i) the program \\(\\Pi\\) halts on all inputs from \\(\\mathcal K_0 \\cup \\mathcal K_1\\), and (ii) the program \\(\\Pi\\) outputs \\texttt{TRUE} for any input from \\(\\mathcal K_1\\) and \\texttt{FALSE} for any input from \\(\\mathcal K_0\\), then at least one of \\(\\mathcal K_0\\), \\(\\mathcal K_1\\) has asymptotic probability zero. The paper is self-contained and accessible, if technically complex. The first fourth of the paper is devoted to a description of the BGS model and some of its properties. Here are some highlights. The paper introduces a generalization of the notion of a random structure of a given signature. It starts with a notion of a {signum}, a generalization of the notion of a relation, and then introduces random graphs, random digraphs, random tournaments, etc., as examples of random signa. Signa are designed for ready application of extension axioms, and the results of this paper actually apply to random signa. It reviews the BGS model of computation, which (very roughly) starts with an input structure of domain \\(I\\), generates the hereditarily finite subsets HF\\((I)\\) of \\(I\\), on which a BGS program defines certain set-theoretic steps for a computation. The number of steps used for a computation is a time bound, while the number of elements of HF\\((I)\\) ``activated'' is used as a space bound. The BGS model is able to carry out certain parallel computations. It is readily shown that there are BGS-computable queries that cannot be fixed by standard extension axioms. Thus they use {strong} extension axioms, which assert not only the existence of vertices satisfying certain diagrammatic properties, but in fact that a certain proportion of all vertices satisfy these properties. It turns out that that all BGS-computable queries are fixed by strong extension properties. Although the BGS model is able to do arithmetic, it is unable to compute unbounded cardinalities withing a fixed number of steps. The remainder of the paper is devoted to a proof of a stronger result from Shelah [loc. cit.]: Let \\(\\Pi\\) be a BGS program (producing a Boolean output) such that for any input, there is a polynomial bound on the number of active elements. Then there exists a class \\(\\mathcal C\\) of signa (of asymptotic probability 1), a Boolean value \\(v\\) and an integer \\(m\\) such that for each input from \\(\\mathcal C\\), either \\(\\Pi\\) halts in precisely \\(m\\) steps and outputs \\(v\\) or it doesn't halt at all. The proof relies on extensive dissection of BGS computations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4457727$45D9D188-F20A-4EBF-9293-7384298A8A38","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strong extension axioms and Shelah's zero-one law for choiceless polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strong_extension_axioms_and_Shelah%27s_zero-one_law_for_choiceless_polynomial_time"}}}}}