{"entities":{"Q922532":{"pageid":924380,"ns":120,"title":"Item:Q922532","lastrevid":65434659,"modified":"2026-04-12T02:33:59Z","type":"item","id":"Q922532","labels":{"en":{"language":"en","value":"Complexity for type-2 relations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4168666"}},"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":"Q922532$4444D251-8957-47B4-AC45-688F1B3FB470","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"42e791446094c275ebd8294580b0f9632fb68c0f","datavalue":{"value":{"text":"Complexity for type-2 relations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q922532$6C9E238B-DD38-430F-A5C9-8A9D156F81B1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9430e6113a324b3340b6cd09557a69f7e55d86ab","datavalue":{"value":"0711.03017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922532$0173A74B-64E2-43BD-807E-F0FD743338D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab5595ba91a24532482472a1dc626e602c7d42f8","datavalue":{"value":{"entity-type":"item","numeric-id":922531,"id":"Q922531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922532$5226D17D-C9B7-48BE-BFA5-EDDC6002D44C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922532$1DA25585-BD95-439C-B283-656059131D9A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q922532$2C69D812-6ED7-46DA-989A-5E429F5C54EB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"274f3909ef25cb808233ea2df711c5a6d525bcc0","datavalue":{"value":"A type-2 relation is a subset of \\((\\Sigma^*)^ n\\times (^{\\Sigma^*}\\Sigma^*)^ n\\), where \\((Y)^ n=Y\\times Y\\times...\\times Y\\) (n times), and \\((^ XY)=\\{f:\\) f is a partial function from X to \\(Y\\}\\). The type-2 functionals are those partial functions whose domains are type-2 relations and the ranges are subsets of \\(\\Sigma^*\\). The paper under review considers the extensions of many classes of ordinary structural complexity theory to the classes of type-2 functionals or relations. For example, the extensions of Poly (the class of polynomial time computable functions), P, NP, \\(\\Sigma^ p_ n\\), \\(\\Pi^ p_ n\\) (the classes of the polynomial hierarchy) are widely discussed. Furthermore, some topological concepts are introduced to type- 2 relations, and it is shown, by topological considerations, that the analogue of the \\(NP=PSPACE\\) question has a negative answer.","type":"string"},"datatype":"string"},"type":"statement","id":"Q922532$CE96C33E-0A4B-488F-B558-294CB911774A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"57eee2f313463199e20b9235bce5c88ea02d3389","datavalue":{"value":"03D65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922532$37B67B5D-4C5E-455E-BEE9-B9BA87ADF8B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922532$334DA9FD-8EAB-432C-920C-64E59AF232C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922532$21BB9D77-3C81-4815-8D34-7BDB5A7C7D48","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e806ffe2ba8410a7ebadbd7b25a3faa23e9e1da8","datavalue":{"value":"4168666","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922532$09CACCAB-00FA-438F-BA85-7322CB66526F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q922532$4CD0F03B-09CD-4818-B745-56C983B7A285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb57ffd39983a08cffc5401c91d66f17a0ea4f7d","datavalue":{"value":"type-2 relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q922532$3FDA3A10-C2A0-4687-B6D7-161A4FCB725D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b801d24b0af0bda88ba8a45aa4cf1aac831bb74","datavalue":{"value":"type-2 functionals","type":"string"},"datatype":"string"},"type":"statement","id":"Q922532$3972CD3D-39AA-401D-8B81-31B30BCECA5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d31be1229374545ff94fd95ad2a5ce9870f120db","datavalue":{"value":"partial functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q922532$7BC95304-2A7D-47F7-BB09-446ECDDA39E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b9523b81abac7dcf2946305ecf06ced9bb8e7c3","datavalue":{"value":"structural complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q922532$B152510E-CBD9-4002-B731-5486E2E18438","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"dbc008852b7f12e01f50414af435612153cc55c4","datavalue":{"value":{"entity-type":"item","numeric-id":162063,"id":"Q162063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922532$C3F22E01-1873-444D-82A4-5ECD8B1918D0","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":"Q922532$AC99F6C2-6355-4CA6-BCEE-5FCB181377DA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"650fb8cfa54538311f09ebf87ae74687ccb569f5","datavalue":{"value":"https://doi.org/10.1305/ndjfl/1093635419","type":"string"},"datatype":"url"},"type":"statement","id":"Q922532$9250B8EA-ECDF-4350-B358-1D7FCE90745D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9f3846c4d0629c0b564629c5cbb2f77a64e38f85","datavalue":{"value":"W2093400121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922532$041153AF-73B1-46EB-A497-9FD322772A89","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"53af41e4e2ab7a83c0e3b08bc7cf58e0009e239f","datavalue":{"value":"10.1305/NDJFL/1093635419","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922532$A28D5486-5ADD-4553-9D7F-2A6FC72F6931","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98327d16b37c521d4a6038b3ac61884e3f6221c6","datavalue":{"value":{"entity-type":"item","numeric-id":4218943,"id":"Q4218943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d85706877678cadfb61f1f1bf303a0f0a33c799e","datavalue":{"value":{"amount":"+0.7816711068153381","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":"Q922532$C4489756-6F2E-4CD6-90C8-5C49FE15A295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a65b7056eaec5a291bd5797a99cd634f45943421","datavalue":{"value":{"entity-type":"item","numeric-id":4673426,"id":"Q4673426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a075609d3cb64d0b97b4bb92d124dd7a5dcbc85b","datavalue":{"value":{"amount":"+0.7735334038734436","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":"Q922532$FEFB8ADC-EAFA-426E-B5FB-182AB828BAC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9559030c76fa4dd0e58ead1cb298ef19b697436a","datavalue":{"value":{"entity-type":"item","numeric-id":4875448,"id":"Q4875448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2fadbfadfdd5727a4566e08f809892cdc64e23a","datavalue":{"value":{"amount":"+0.7644334435462952","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":"Q922532$B8116BBF-F755-4E30-A17A-99E47722F88D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d0ae397e1f6cb1d42840dc2b18965ea92058d66","datavalue":{"value":{"entity-type":"item","numeric-id":4010352,"id":"Q4010352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddfd06777b5fa015b6831b25248873cff308f53f","datavalue":{"value":{"amount":"+0.7511776685714722","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":"Q922532$9F9BEE3A-FD23-444C-AE01-196082AD3B96","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity for type-2 relations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_for_type-2_relations"}}}}}