{"entities":{"Q1125059":{"pageid":1135808,"ns":120,"title":"Item:Q1125059","lastrevid":66815928,"modified":"2026-04-12T13:03:05Z","type":"item","id":"Q1125059","labels":{"en":{"language":"en","value":"Choiceless polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1371589"}},"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":"Q1125059$067847EE-3055-4BAE-8E90-C62A1267147A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a5220f8922dc0e9b40c646f41f843a7236752321","datavalue":{"value":{"text":"Choiceless polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1125059$484B0498-EAFC-4130-99A6-122E7325E141","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1ccb47571c8e42b37479817bafa10e707b9e42ca","datavalue":{"value":"0936.03037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$6C9229D3-0A75-4964-AC8F-BA7497B563DB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7c83e8f2b22b3b0d7ab7c26cff335e3a0b549136","datavalue":{"value":"10.1016/S0168-0072(99)00005-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$ADFF0AF7-C648-40C8-8707-E847AC9ECF71","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":"Q1125059$D3B15F53-7357-4000-8CD9-52C7E3C86335","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":"Q1125059$2550E2D3-D81A-4793-A3DA-A1EE2CE8DFF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8259050cd83ce3945f173c3e3c741cd5ddddec01","datavalue":{"value":{"entity-type":"item","numeric-id":169248,"id":"Q169248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1125059$95B37EEF-CA2F-48DB-B4E6-B64CA4DF2271","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":"Q1125059$FA156CF1-0F3D-4F08-84AF-A8910E5811BF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eabf40ae2ce7091a866094c302ce82489d929ba4","datavalue":{"value":{"time":"+2000-04-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1125059$9C8B8A81-78EB-40BF-A400-14605B6A5AC3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c75235ea006be6a64472ee2824b840e822f7e216","datavalue":{"value":"https://arxiv.org/abs/math/9705225","type":"string"},"datatype":"url"},"type":"statement","id":"Q1125059$A3B0A309-A014-41C2-9532-A4CE4491A56E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd2c27499e91ac09a61b03e7c99cc75c9c4aa8b5","datavalue":{"value":"Problems in combinatorics, database theory, etc., whose computational complexity we want to examine, are mostly naturally defined as sets of structures (graphs, relations, etc.). In order to use machine models, as, e.g., Turing machines for this study, one has to encode structures as strings. This, however, leads to the problem that there is no known, easily computable encoding that does not distinguish between isomorphic structures. The authors examine the question if there is a computation model that operates directly on structures and that captures the class PTime (polynomial time) over structures. The model introduced here (a form of abstract state machines) is as powerful as any other model introduced in the literature for the same purpose (for example relational machines, see, e.g., \\textit{S. Abiteboul, C. H. Papadimitriou} and \\textit{V. Vianu}, ``Reflective relational machines'' [Inf. Comput. 143, No. 2, 110-136 (1998; Zbl 0918.68017)]; \\textit{S. Abiteboul, M. Y. Vardi} and \\textit{V. Vianu}, ``Fixpoint logics, relational machines, and computational complexity'' [J. ACM 44, No. 1, 30-56 (1997; Zbl 0883.68070)]); it even appears to be more powerful. Nevertheless, it is shown that it does not capture all of PTime (examples for problems in the difference are parity and bipartite matching). The captured fragment of PTime is called choiceless polynomial time, because it is shown that it corresponds to polynomial time where arbitrary choices (i.e., pseudo-code statements of the form ``choose an arbitrary \\(y\\in Y\\)'') are eliminated by means of parallel execution. This of course only has a real effect for problems where the resource bound prevents the computation from trying all possible choices. Some extensions of choiceless polynomial time (that again do not capture all of PTime) are examined.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125059$0211B600-3C72-42A6-B740-8370862D7BE7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cda603722202722f19339c0e84295bbe19098fb","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1125059$8C5543AC-0038-4B80-B132-0697FEB6ABF0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$3FF05121-EE40-4C6E-89E2-0292CAE1B37D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$0C6963A5-8134-4246-A6A1-2220399884B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$36FDBF6F-8991-437C-9A2F-C6FF83B521B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$D6B1AB68-50E7-4457-96AA-D7170BD27198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$918A99F1-D264-43ED-90BE-B03F9D2D538B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$2595AF33-0F6E-48D5-940D-E58F618D8FBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$8D17D920-22B0-41AD-BCA8-D2F41021BD4A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"106a5d069350b70b2286714966bc9bcace55ca22","datavalue":{"value":"1371589","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$0C540FCA-16BD-488E-B2CB-FB82571411C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125059$EB7C837E-B7BC-4D09-82F5-F49F155944FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6db2953c02516cbc73608b94a6bcdd7e31e2a10","datavalue":{"value":"PTime logics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125059$4AAA76D5-A685-475F-B83B-4FD44F2DBF65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf00e43fd6ab092796109964f1a55fca40cc53e","datavalue":{"value":"abstract state machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125059$A7360346-1581-423B-9925-87CA8F04B27E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30aded0552094ac5716fe4747a6c670c61574792","datavalue":{"value":"choice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125059$23AAD948-03A9-45CB-87C5-0105D6C740D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5363a43478db45b4fe7ca9bf2ddd9319c05c5363","datavalue":{"value":"parallelism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125059$5FD2C786-6D17-4962-85CE-4577A0842408","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7bca72283e90ce07e98bad6bf84df2b41dfffc31","datavalue":{"value":"Q105978985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125059$5287BF53-81F7-4D1F-B4D9-06C84163FAD5","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":"Q1125059$6197E9F8-B0A0-4503-A0E4-ACC9B78732BE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a99d55e78c140053cbb1a1ff3efd4a5e1fa4fa5","datavalue":{"value":{"entity-type":"item","numeric-id":4381707,"id":"Q4381707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51343fa0cbcdffc2a4ad5c6d8cde45b31a85188d","datavalue":{"value":{"amount":"+0.8341287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$F5B68421-0875-453E-B5BF-797A5DBA7872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dba7f4e1428ae06babb11d7118852a8dd204dd26","datavalue":{"value":{"entity-type":"item","numeric-id":1271557,"id":"Q1271557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fde3cf347afdf8fc9270fdbe98cb24ced61c9fc","datavalue":{"value":{"amount":"+0.80997795","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$A96A85AD-C56E-476E-B47C-B084ED4DB97C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"762ae9f7f8293efb0c9059591f6a4d729a1ede94","datavalue":{"value":{"entity-type":"item","numeric-id":2807086,"id":"Q2807086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0f0531ad7a15838998f4bef9ee1d0e7d1c4ec42","datavalue":{"value":{"amount":"+0.8069186","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$D586776F-2B88-42AA-B472-FF8A075854EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82273606020bb712f13c695c2025cb4eeb3af360","datavalue":{"value":{"entity-type":"item","numeric-id":4371697,"id":"Q4371697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e88e33483637c6ac8e241d3d48904ee4456b9a13","datavalue":{"value":{"amount":"+0.7797144","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$5CED7293-4F54-4D4C-A2D3-5A970CB0C4E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66ee2ab358d0e00d778f3a61c51903bf88b3fcfe","datavalue":{"value":{"entity-type":"item","numeric-id":4472219,"id":"Q4472219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4728bfb97f9c7ad49d00c64dd7e34c5701137a67","datavalue":{"value":{"amount":"+0.7790762","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$0E5FBA7B-3E45-4B8F-BFF3-30B6E7CCC7B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91fc6531fad47a9b7c43f6e632d7db545569f604","datavalue":{"value":{"entity-type":"item","numeric-id":4779654,"id":"Q4779654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"338a19b0f4db81c9b6a711fa0c281e7bd88c5e3a","datavalue":{"value":{"amount":"+0.7375136","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$2EBC7782-44A7-4BBD-BDC6-F8DDCB7886DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c85214c6893aa6423eadb5a8f3d755e72e01953","datavalue":{"value":{"entity-type":"item","numeric-id":3753525,"id":"Q3753525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1e0f5c88d684df4e93843d40a410d0e21b5d67b","datavalue":{"value":{"amount":"+0.7365047","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$143C60BD-1EF0-448F-A050-D7BE08BFFE1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"588ac61643b7de1d9e2a9c4c210b0bc3d438becb","datavalue":{"value":{"entity-type":"item","numeric-id":5269008,"id":"Q5269008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"711b14ead6ca79ecc76c241c9d0de4a2014e914f","datavalue":{"value":{"amount":"+0.736447","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$2401E521-79E5-4A4C-98DB-9AD9146D1509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc7937d3b21bf961fd398e0c9a52d738af39e519","datavalue":{"value":{"entity-type":"item","numeric-id":4415085,"id":"Q4415085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"708ec55498fca7a33670775e8e98a36e2e54f38a","datavalue":{"value":{"amount":"+0.7363411","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$26130150-9628-4782-87D5-78C6913E7816","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1be530d9f6874731a091363f2897afc7b1a44642","datavalue":{"value":{"entity-type":"item","numeric-id":4916216,"id":"Q4916216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7cd80b3c3d68461d2d43ee3975b9bcffc5a15d7","datavalue":{"value":{"amount":"+0.73092985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125059$026A2910-AFF9-4D6E-A732-30A5B457375A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Choiceless polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Choiceless_polynomial_time"}}}}}