{"entities":{"Q1109566":{"pageid":1120315,"ns":120,"title":"Item:Q1109566","lastrevid":49210021,"modified":"2026-01-06T18:47:17Z","type":"item","id":"Q1109566","labels":{"en":{"language":"en","value":"Complexity classes without machines: on complete languages for UP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070310"}},"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":"Q1109566$32FDCDB3-2E84-48D9-B4B4-3911F82EB71F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"85517acab3ddf2942086663b6ddffc6ef02ff1c1","datavalue":{"value":{"text":"Complexity classes without machines: on complete languages for UP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109566$8F90A734-9795-42B0-9098-2F6786FA6A4E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e87bc912d353b8ef8c45a06b9d22740338fda6c4","datavalue":{"value":"0655.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109566$56F47C29-E50F-458C-A86E-5A43F514CCC8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f078caa99e4af8e4edcfc75e34eaebde2d80fcb6","datavalue":{"value":"10.1016/0304-3975(88)90022-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109566$B310F55C-F35E-4DA5-B2E2-09062FD5411D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f24581060e1fc674d2a5c7705dc19743c7374ca5","datavalue":{"value":{"entity-type":"item","numeric-id":1071499,"id":"Q1071499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$1355E0D5-B0C9-489F-A2E6-CE51A49FDB61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95d207a16ce6533a2e03f4685944467ead41f45c","datavalue":{"value":{"entity-type":"item","numeric-id":161382,"id":"Q161382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$623022B2-2B61-4205-A76F-F7990F958BB6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$308508E8-A08A-4D43-B079-A4A24147E28B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1109566$FBE61340-09AD-4FD8-B1BE-F0F17ADBDDF0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"311bb21750f8d268d2098a4c54f592fff76db54c","datavalue":{"value":"https://hdl.handle.net/1813/6586","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109566$8D2DC9CA-3C07-4F60-A93A-5FEF91603648","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7a0bada8ff21cd97fd46c0db7814a6f9ead9d6ad","datavalue":{"value":"An NP language is in the class UP iff it can be accepted by a nondeterministic polynomial-time machine with unique accepting paths. It is shown that there are relativizations A and B such that UP A has no complete languages, while P \\(B\\neq UP\\) \\(B\\neq NP\\) B and UP B has complete languages. Necessary and sufficient conditions are given for UP to have complete languages, for \\(P\\neq UP\\), and for \\(P\\neq UP\\cap coUP\\). As an application of their techniques, the authors show that there is a recursive oracle A such that BPP A has no complete languages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109566$B315B148-9E5E-4690-940E-7617D7407556","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109566$250E106D-CC9E-40E3-B2CD-46B88F788427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109566$2D2EA8B4-B054-4CEF-A69C-925602440EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109566$E097FDA6-6C9E-4E33-8956-6F6D561B7905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109566$797D6CA8-E11C-416E-ACF1-D593D8877B7F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dc9f18f97560a29a31847c8b10edfa6b95abcd9b","datavalue":{"value":"4070310","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109566$0C90C1B5-656F-4BFD-81C6-4B83C6ABEE26","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9300412c53a1c3845cb609659673134c574086b","datavalue":{"value":"counting class UP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109566$576BE649-A9B3-4419-A7C1-1917AE0EA9B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44dfd03a7026372ab89fca65813e83ed327a1ea9","datavalue":{"value":"probabilistic class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109566$D182989D-2619-4900-B0F5-2F086E4948A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109566$BE175808-99DF-4635-B3C5-E65C5F6E5A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64b4a1c903bdbad63491df93be09359d9b4e135b","datavalue":{"value":"unique satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109566$201523F9-B963-4FF0-A80D-4E53B642A3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d95edd6b76b4bdb73d152904f7825e8f74ba3b4","datavalue":{"value":"BPP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109566$2C1337CC-25A6-4B9E-BD10-C17431A15A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79f45fba1d9a2dd7228d7987af275a1de025bb21","datavalue":{"value":"unique accepting paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109566$1131D1E2-4AF6-44E7-A48E-89EBD634D261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b15ec6e8c53b774a9514991af298a7f8fabce45","datavalue":{"value":"complete languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109566$66AB7577-333C-45BF-9B35-3FFAE6F71A31","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e860208dea0a8f07f1622b3764a2f40159457c4c","datavalue":{"value":{"entity-type":"item","numeric-id":186051,"id":"Q186051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$9DC7E3D1-D2D9-430E-8DF2-189589F9A0E6","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":"Q1109566$7D07AE9B-568A-4858-85E5-EC0F9459117D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"db4a658d662d2e76a0705d97b0a8fc962e9efb68","datavalue":{"value":"W2100570449","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109566$A58BB92D-F41E-405E-8A21-91CCB198EC31","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c317ee9b89d25866849eff84487be5a7c7991b60","datavalue":{"value":{"entity-type":"item","numeric-id":3331209,"id":"Q3331209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$E27FCCBB-100D-48D3-A893-BE454C9C0880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$10492D5C-7661-4C7F-B7CB-95E8F635511C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$12E43C3D-6675-45CE-B064-E84F95DB1D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d5257f71d98a6e1899a8d1ff1a09a30fa28cbba","datavalue":{"value":{"entity-type":"item","numeric-id":3751004,"id":"Q3751004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$54CD59A3-0375-4852-97AD-1B73D22AF3AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bcb11f0b30802ff1fa8b04ab34822dc12429034","datavalue":{"value":{"entity-type":"item","numeric-id":3832042,"id":"Q3832042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$B28C0B96-3D14-4F76-A015-33A94D563251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$48712F76-7822-453D-8B3E-53776954958A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$2C87906A-58B3-479A-9DDD-11DB219A96A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$9F4D8FE0-8D56-4C1D-BF90-2BDDB6642605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adc67edbb1677ad77489d6c17db913a838f0b011","datavalue":{"value":{"entity-type":"item","numeric-id":3696516,"id":"Q3696516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$1F276667-4E06-4C49-B9E6-DAA82C4078AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$5EACE0A9-B40F-446D-80F5-D6A59247A30F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb51cb599580481aadcbb3a7e805e65dbcbf5ce5","datavalue":{"value":{"entity-type":"item","numeric-id":1079364,"id":"Q1079364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$57A00D96-026C-44D0-A6C6-09111D46A71C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93d33a8bea03e38d0829c039acfebe8d2d278a62","datavalue":{"value":{"entity-type":"item","numeric-id":3676130,"id":"Q3676130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$827D3846-9721-403A-9080-772BC944D8D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb2c936121f4f1d6e6f7ab70089a797e73426bb","datavalue":{"value":{"entity-type":"item","numeric-id":3662618,"id":"Q3662618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$26B40D90-B1BE-4F44-93A4-DAA3D6E85A4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3fdeac57e6ae30181fb2db5f7f4e10e134e5670","datavalue":{"value":{"entity-type":"item","numeric-id":1232181,"id":"Q1232181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109566$644C49C5-0CAB-4BD0-9896-E097A292AF74","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27ab7d4690c1fb3a38834b717839879c7b9df99c","datavalue":{"value":{"entity-type":"item","numeric-id":4873687,"id":"Q4873687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"004c14bcbe9e6c66fb7946fdd4aa889417e29b7a","datavalue":{"value":{"amount":"+0.8572190999984741","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":"Q1109566$03121068-3115-4E8D-B4FD-D294C16EBB5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77374390b02a3ab47003016d40f98a29eb7c39bf","datavalue":{"value":{"entity-type":"item","numeric-id":3824299,"id":"Q3824299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0330bdd53ddcb7951cc1cfe238fd826d5af4bb08","datavalue":{"value":{"amount":"+0.8081037998199463","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":"Q1109566$CD5579D7-55A5-41C9-BDDD-96E5DFB1F651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b997d303539924e0b5a2f53c48a1152989cad592","datavalue":{"value":{"entity-type":"item","numeric-id":3201755,"id":"Q3201755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ca07d65b1b3e92a20688637be304a3001107ec2","datavalue":{"value":{"amount":"+0.7935034036636353","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":"Q1109566$08C900A4-9BD0-47DB-8A81-508DA270C155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74d41faea6c95f62f8067b601345d4c9c9aa5837","datavalue":{"value":{"entity-type":"item","numeric-id":4895813,"id":"Q4895813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9464a9f517e49c4a4227eba6d1492313b660eb02","datavalue":{"value":{"amount":"+0.7795907258987427","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":"Q1109566$58D8A73E-1427-4734-B31B-BBDD476E6CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d9031b73ffb0f4c256e887d2438ff51cf9e7d9d","datavalue":{"value":{"entity-type":"item","numeric-id":3761699,"id":"Q3761699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8298d8e65c5466f481895519ddbed4e6a15415f","datavalue":{"value":{"amount":"+0.7764824628829956","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":"Q1109566$7E3F7656-62F8-40C6-ADA6-7775872A0BA3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1109566","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1109566"}}}}}