{"entities":{"Q2465291":{"pageid":2476034,"ns":120,"title":"Item:Q2465291","lastrevid":44141145,"modified":"2025-11-20T08:08:11Z","type":"item","id":"Q2465291","labels":{"en":{"language":"en","value":"A note on parallel and alternating time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5224946"}},"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":"Q2465291$C26B92B8-677B-4A82-96FC-40FC425641FB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"72e8cae42f2ba47f252bb569958c1e7e0da562ab","datavalue":{"value":{"text":"A note on parallel and alternating time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2465291$B962534D-79B2-492D-98F6-3CCC74BE93D6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a287a6dd763809b28124bf8949cbaa9652dacba4","datavalue":{"value":"1137.65076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2465291$AD975425-E59B-4EDB-B3F2-E032D893DDE7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c2e1176b7e05a6aa00019f286dc7036ccdb20da","datavalue":{"value":{"entity-type":"item","numeric-id":199198,"id":"Q199198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$939B5B69-247F-4439-91E1-5149A4F5E658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"03aad0d1a79d8c7d4865d4e5fdd30aadd4f645cc","datavalue":{"value":{"entity-type":"item","numeric-id":617889,"id":"Q617889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$9C9206BD-7261-4261-B02D-5A586DE6E604","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$2C0B9E3F-1195-47C0-8598-D5F5A835647F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"199bc4b5aae8aea851d1277c2affc2eece2d31d8","datavalue":{"value":{"time":"+2008-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2465291$787A95E4-34C6-4B8F-BCAF-974461A3F17D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa6ca986debece198b986fce527307f250243c7c","datavalue":{"value":"Denote by \\(\\text{PSPACE}_{\\mathbb R}\\) the class of sets of real vectors decidable in exponential time and using polynomial space; by \\(\\text{PAT}_{\\mathbb R}\\) the class of sets decidable using polynomial alternating time; and by \\(\\text{PAR}_{\\mathbb R}\\) the one of those decidable using parallel polynomial time. The goal of this paper is to investigate the boundaries between these notions by looking at quantifiers with a restricted expressive power and considering the classes they define. More precisely, the studied quantifiers are the digital quantifiers for which the above classes are naturally modified.   The first main result is that \\(\\text{DPAT}_{\\mathbb R}^{\\text{PH}_{\\mathbb R}}\\subseteq \\text{PAR}_{\\mathbb R}\\), where \\(\\text{DPAT}_{\\mathbb R}\\) is the class of digital polynomial alternating time and \\(\\text{PH}_{\\mathbb R}\\) denotes the polynomial hierarchy over the reals. The second main result is that \\(\\text{PAR}_{\\mathbb R}\\subseteq \\text{MA}\\forall_{\\mathbb R}\\) and \\(\\text{PAR}_{\\mathbb R}\\subseteq \\text{MA}\\exists_{\\mathbb R}\\), where \\(\\text{MA}\\exists_{\\mathbb R}\\) denotes the class containing all sets decidable alternation digital universal and real existential guesses in polynomial time. Similarly \\(\\text{MA}\\forall_{\\mathbb R}\\) denotes the class contains all sets decidable alternating digital existential and real guesses in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2465291$A5C4D157-A9C5-492B-A52F-0E3B0E0F9530","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2465291$EC7EDC6B-781D-40D5-A658-86D4C82F00E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2465291$3D267FB0-2300-4E7E-B369-A5B9DF4335D0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a9d70ada130b0dbcf78c72b48b1db8e53c8cfcbb","datavalue":{"value":"5224946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2465291$2520EAC5-483E-4FB8-A984-1BB203AF372E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2465291$5EF51C77-25E5-4E26-9295-830E94D21F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5363a43478db45b4fe7ca9bf2ddd9319c05c5363","datavalue":{"value":"parallelism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2465291$3C0782AB-AC88-400A-9E7A-52DD93FACA20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8248a1dce4178bcbdf50d1b921f9653b658d3d1b","datavalue":{"value":"alternation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2465291$7543C6AE-5817-4ABB-A568-A854B3D20BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1d12e51f7d2438567b51bfce46972f6255ef9f3","datavalue":{"value":"exponential time","type":"string"},"datatype":"string"},"type":"statement","id":"Q2465291$6DECECC0-95C9-4221-B58B-58C58CEEC99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67850f6fec23abd3871f7c36488ce87058033e65","datavalue":{"value":"polynomial alternating time","type":"string"},"datatype":"string"},"type":"statement","id":"Q2465291$557D3FEE-5B03-40A4-A15B-FBEF79A12E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"974d3b42fc7114b6a1fe4b7f259b42cb6595e1fd","datavalue":{"value":"parallel polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q2465291$F7F20A97-E33A-4BC5-91DB-798B038076DF","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1e3e2a2c998e2a15625bbb994eaa37a82dcf7c8a","datavalue":{"value":"Q57733161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2465291$E520EC0F-D516-4BDD-B079-A0B45FA8AEED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b97ffffc5c648bc1b9503f87cfea61b9d21adb18","datavalue":{"value":{"entity-type":"item","numeric-id":169458,"id":"Q169458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$065140C5-5E56-466C-BF9E-C743EBA973A1","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":"Q2465291$49FF92B6-F39A-46A3-866D-899014974F6A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"100658f48180f1cadc5f2a2dba60666f448e0240","datavalue":{"value":"https://doi.org/10.1016/j.jco.2007.02.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q2465291$9DCE4C8E-B51F-40DD-A31F-3625F052A4BF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2056532cca973677fd1b5cc73e0993813c8b3328","datavalue":{"value":"W2055415340","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2465291$3967AEB4-AEDC-4B98-BE9D-C4A349506605","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1efc6d224ffe0d7322355df220a9a0a92863a911","datavalue":{"value":{"entity-type":"item","numeric-id":4729768,"id":"Q4729768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$0127D691-E9C0-47F8-86E7-911BCAEA66F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e86a79bfcfca810fb7601492bd0551fae9de8408","datavalue":{"value":{"entity-type":"item","numeric-id":4142697,"id":"Q4142697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$9FBBAA90-D25D-44D1-9A48-1952F3402FB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d31447a07e80c99e4bc09df2e12ef4a3e1470ab5","datavalue":{"value":{"entity-type":"item","numeric-id":3140550,"id":"Q3140550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$F9897F68-C3EC-48F4-B64D-CE09F8A4279D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54d47dc940bbfa0a343c58cd01abae7f930d7f38","datavalue":{"value":{"entity-type":"item","numeric-id":4717055,"id":"Q4717055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$C2DAA021-3A60-480E-BEC8-CE6FC724AC9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16c36fcf94b4e609e7e02b635bd5008c838085f7","datavalue":{"value":{"entity-type":"item","numeric-id":1338219,"id":"Q1338219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$A38DF3A8-C591-4304-A3B8-2BE7565348EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bc8f298894a9c0b055facda7a0acdd72eb476f3","datavalue":{"value":{"entity-type":"item","numeric-id":4729767,"id":"Q4729767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$6283EFC1-5D40-488E-9A1D-BABF9A2BE384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19dff2c4019038a537dbca7200a9dc3c42f75370","datavalue":{"value":{"entity-type":"item","numeric-id":1185457,"id":"Q1185457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2465291$160F23A0-AE25-4F5A-A0A2-919B3F508977","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"3fc1a23a8a5aa9e91f2a9d80ed7bac6dbb39f4c4","datavalue":{"value":"journals/jc/CuckerB07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2465291$0E3A22B9-978C-4CB7-9A65-A89D45A2FBCC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"433516d8d03dc9662583ad908fb633ca975ee92b","datavalue":{"value":"10.1016/J.JCO.2007.02.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2465291$51E1BBA0-F1F6-4FD2-A2EB-7E9C3BBC1A5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d6be0a755e2b37fdf855f4c1e99b66ea5360b81","datavalue":{"value":{"entity-type":"item","numeric-id":4717057,"id":"Q4717057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"674373c9bd068543f7a714425c8003e779039afa","datavalue":{"value":{"amount":"+0.88003415","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":"Q2465291$FE45B725-A25A-47E1-9470-55325D2A698C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0e82a4af6e4966bfeae507c38a64ca61fe500c3","datavalue":{"value":{"entity-type":"item","numeric-id":315457,"id":"Q315457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"990b17d77736ffaf3e282dd417f2545ad8ff10d0","datavalue":{"value":{"amount":"+0.8672549","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":"Q2465291$40D0A38C-2B19-4846-9FAA-AE1251EA915C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3edb4a78673c0de969fd9e9baa45af573325a23","datavalue":{"value":{"entity-type":"item","numeric-id":5435040,"id":"Q5435040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7d30e137cb7824b604068d73063cbd24f461a8e","datavalue":{"value":{"amount":"+0.867147","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":"Q2465291$D703ED44-28EF-4396-8729-0EC8E8316835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f971504068f9f6a2a166eda2076132369b0de84","datavalue":{"value":{"entity-type":"item","numeric-id":3528654,"id":"Q3528654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5892c995cb3bea4aa6456db1b16c9877a2806306","datavalue":{"value":{"amount":"+0.8521624","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":"Q2465291$C385BFCC-B426-495F-891F-BB0197EDD19D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ce78b830281d94f6f450e0cc07138baafcdef70","datavalue":{"value":{"entity-type":"item","numeric-id":5439577,"id":"Q5439577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f49f97bd615bfc22750d647a73eec2cb97a11dce","datavalue":{"value":{"amount":"+0.8339044","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":"Q2465291$95AD3F05-1428-47F0-82C5-023A69E71794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6e28d22eed9648f147179eb00362e51db3d6430","datavalue":{"value":{"entity-type":"item","numeric-id":925731,"id":"Q925731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ef15f10c96784152eaf96e82c7a3eaa0a184fff","datavalue":{"value":{"amount":"+0.828765","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":"Q2465291$516A81BB-16DE-4D00-B3F9-909182AE8D50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f4403532688b7c364c13451d328bd68ee2ba742","datavalue":{"value":{"entity-type":"item","numeric-id":6163822,"id":"Q6163822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4925853e2d9282bd3ac89dd92aee6bf932fb1f9","datavalue":{"value":{"amount":"+0.82069176","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":"Q2465291$D392B584-27F8-4E7E-A35C-1B0EEACF5C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f30fa90066e82197b4a895c1c1ebf9b047e9dc72","datavalue":{"value":{"entity-type":"item","numeric-id":6044116,"id":"Q6044116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81ac67459cffd5becd0b65651d2c843680e58b77","datavalue":{"value":{"amount":"+0.82037455","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":"Q2465291$F90D8E8A-F97E-4401-AA34-0BC9CD6E03BD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2465291","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2465291"}}}}}