{"entities":{"Q790804":{"pageid":792652,"ns":120,"title":"Item:Q790804","lastrevid":42697254,"modified":"2025-07-08T14:16:05Z","type":"item","id":"Q790804","labels":{"en":{"language":"en","value":"A normal form for arithmetical representation of \\({\\mathcal N}{\\mathcal P}\\)-sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3849209"}},"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":"Q790804$4744B0FB-8CCC-477C-9C4B-BAEFADC076A7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e81bc444140e8676120160b503281032fb0b9852","datavalue":{"value":{"text":"A normal form for arithmetical representation of \\({\\mathcal N}{\\mathcal P}\\)-sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790804$4A47E03C-EDF0-414C-8ABE-FA607DBB68D1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aefccbf5a372d034334fff217f6963ec9e28ed67","datavalue":{"value":"0535.03016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790804$3098AD2D-B539-4847-86A4-AB2C7C58A3CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"85aed954e661b1fd7eb0b769dbebe95b308edebf","datavalue":{"value":"10.1016/0022-0000(83)90048-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790804$5269B61D-C1AF-46A5-B92A-B9512E4EA7B5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cfe7feb0a9f29a12954c6b9a9eea15a480f4f85","datavalue":{"value":{"entity-type":"item","numeric-id":790802,"id":"Q790802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$D7A0C525-79F8-4D0F-B4AE-A5D62ED211F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5342853198866e12b3d7b6e7cf2193caff1d15f","datavalue":{"value":{"entity-type":"item","numeric-id":790803,"id":"Q790803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$F68EED51-EA51-4E0D-A4B5-4C09104DE1EC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$F82A03F5-AC2C-4075-9C22-0117CF0132AC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q790804$F9043090-DF9C-4838-8A3B-258B70A600B7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"26d845ea97c13dc994cd4b6931be67f2c1dc06ab","datavalue":{"value":"In a previous paper [Theor. Comput. Sci. 21, 255-267 (1982; Zbl 0498.03023)] the same authors have obtained an arithmetical characterization of the class \\({\\mathcal N}{\\mathcal P}\\) in terms of ''exponential existential bounded arithmetical predicates''. Here, this result is strengthened, i.e. it is proved that all but one of the bounded universal quantifiers can be eliminated. As an interesting consequence, we note a relation between the polynomial-time hierarchy [\\textit{L. J. Stockmeyer}, Theor. Comput. Sci. 3, 1-22 (1977; Zbl 0353.02024); \\textit{C. Wrathal}, ibid. 3, 23-33 (1977; Zbl 0366.02031)] and the diophantine-hierarchy [\\textit{L. Adleman} and \\textit{K. Manders}, Diophantine complexity, Proc. 17th Ann. Symp. Found. Comput. Sci., 81-88 (1976)]. This relation is obtained via a new hierarchy - the polynomial matrix hierarchy - introduced in the paper under review.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790804$1C15A67B-A6AF-4B38-9584-680F7C73459E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790804$0EAE6860-F497-43B2-A7C7-FC9EC9AB485D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790804$53757E26-42C3-4ABE-B4E1-C2C23D465234","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd4311ec3640f8b0596911d8c87650d0f15580ce","datavalue":{"value":"3849209","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790804$CDA900D7-9B14-4E1C-B0A8-F3F0C9DD4962","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"319f7aef6d48907b019428ced327b73484cf6132","datavalue":{"value":"polynomial-time hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q790804$49F9D68B-1195-429B-98D1-3B7CACBBD2A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca601c346cf0bc15c5ded3d2eeb0091579525548","datavalue":{"value":"diophantine hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q790804$ADAC2281-3939-4794-B7AF-56FE78E3B91A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6289c359a009a47005ba795c27f3bc5518d87c7","datavalue":{"value":"polynomial matrix hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q790804$8B4A5BB3-C3E5-493F-AD97-A99EA7FCB9B6","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":"Q790804$DDD42844-D0D7-46B3-B893-8ED5F8F0BD12","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$4E2124EA-3D4C-4D74-AA8E-22A6CEDF7093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"012b1d6c0f10a6942b99540dd3ba9e03f65c4e47","datavalue":{"value":{"entity-type":"item","numeric-id":5820550,"id":"Q5820550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$B1651F97-674D-4B21-A5D9-25A63EEDD13F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6db44461333ef5e5aae7abb248658a05e60ef41","datavalue":{"value":{"entity-type":"item","numeric-id":3247126,"id":"Q3247126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$3ACA14C2-D661-4AA7-93BB-65BADDA7E264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175c1c6339231426570e05a46d3193da46e70701","datavalue":{"value":{"entity-type":"item","numeric-id":4401926,"id":"Q4401926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$917E3109-1ADB-4B9B-A887-FB01FE05BABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeb89c68e650c350803663393d6e0912dfa3f4b2","datavalue":{"value":{"entity-type":"item","numeric-id":4115143,"id":"Q4115143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$EFEE359D-9FD2-450A-B37D-E59F9B369594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dde8568336ae0db47267f92475d7638fe0ab9a7b","datavalue":{"value":{"entity-type":"item","numeric-id":3937379,"id":"Q3937379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$5D1D44AF-719F-42C5-A496-EF033357278A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$5D3F526F-5F70-4C49-8BC0-B7BCB0A657E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5d9257bacf9dc83d7699c2f8365feb77fa5cc2c","datavalue":{"value":{"entity-type":"item","numeric-id":1171050,"id":"Q1171050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$6854251A-BFBC-496F-A182-346627F13930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61723c3df80f3980ce5d1ecc4aefe9f7748f50f5","datavalue":{"value":{"entity-type":"item","numeric-id":1243130,"id":"Q1243130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$C6EE101E-E0BD-4A4B-B7F8-2ABC9549F2F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1e4bebc0d3492458216eb2f64c777cb3b66be1d","datavalue":{"value":{"entity-type":"item","numeric-id":1147132,"id":"Q1147132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$B4F66632-32C2-4029-AD96-E5773FB6C88E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da7043099d9dc243fe3bc132bb2bd547b572a587","datavalue":{"value":{"entity-type":"item","numeric-id":3235358,"id":"Q3235358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$ECC8B839-9C3B-44E5-9A99-1A2FFA80FEED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3065df023fcb2411980df376c6fc4777f5d291a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241440,"id":"Q1241440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790804$F2B9ACF1-2BA4-40F8-B9FA-340ADBE06C23","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f979b7b5570ed8757b7ccb2ab14cc764333067ef","datavalue":{"value":{"entity-type":"item","numeric-id":4486451,"id":"Q4486451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd2fc3ded41dcf81d881f60db44b340bd1de2da7","datavalue":{"value":{"amount":"+0.8535042","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":"Q790804$780785BE-D6C3-4532-9A85-FBA764105BB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"705e116050a0b7d8bac2dd51199a018f56175755","datavalue":{"value":{"entity-type":"item","numeric-id":1375747,"id":"Q1375747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb2a617cc55b883e312fa71cc0cc9ef5f34fc422","datavalue":{"value":{"amount":"+0.8532699","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":"Q790804$A5A4B2BB-2160-4028-B2DD-B12A018683D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e722518352b18c101a192343b6df1fff6723e0ed","datavalue":{"value":{"entity-type":"item","numeric-id":693054,"id":"Q693054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf8edc992e9d15a9d00d0fa01f5ffd805f54c580","datavalue":{"value":{"amount":"+0.8523989","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":"Q790804$07C4E7D3-0934-4B06-918C-CDC9D8E0DBED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e8a3041ec8fd7a54ae82689a9910a3e72dced0f","datavalue":{"value":{"entity-type":"item","numeric-id":3025326,"id":"Q3025326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d333cfb25c90abd15f2577ad1147c20d317c628","datavalue":{"value":{"amount":"+0.84182787","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":"Q790804$6FD5AEB9-3BFB-48A6-9B44-E48E67AF6965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58cce5f1a85892e16b6b666e6c1a354be2b34a8a","datavalue":{"value":{"entity-type":"item","numeric-id":5015727,"id":"Q5015727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89f88da66a45ff8db9cad50183cd968d8c469a35","datavalue":{"value":{"amount":"+0.84170866","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":"Q790804$BF2FF59F-9E77-449E-87A9-89487FEF8B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48b63b1622a868ca9d3d52c833b3c3655997d748","datavalue":{"value":{"entity-type":"item","numeric-id":3153291,"id":"Q3153291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"168292e5a9cf98a77789de5646a7423dce71df05","datavalue":{"value":{"amount":"+0.83943117","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":"Q790804$CEF8D10E-0DEC-41E0-A233-3D29D54CDFA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1da468fe9d8ddbb0d21516063639e98804194fab","datavalue":{"value":{"entity-type":"item","numeric-id":539193,"id":"Q539193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"446b0a0b5d676cce37fa92db8101956bdb02e19f","datavalue":{"value":{"amount":"+0.8392041","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":"Q790804$A4646BBC-14C7-48CE-8C2A-7EA73A34FB1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d857abff7a51364d07e0b2cae89e8340a6868df","datavalue":{"value":{"entity-type":"item","numeric-id":976545,"id":"Q976545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf387ea8fa37ad11244b9a8cf90b8f7d8d3384b8","datavalue":{"value":{"amount":"+0.8385967","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":"Q790804$C818D874-71C5-49F7-A19C-0BC43AA62BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ea51d3ad0d98f7994b6d1df4b5ad1dd5c6a0a1b","datavalue":{"value":{"entity-type":"item","numeric-id":5950983,"id":"Q5950983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45ea10fe8e785b7a0d071a4a5c09c0c0904268c0","datavalue":{"value":{"amount":"+0.83796096","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":"Q790804$78231F57-6E94-44B9-B78A-1C940B057E99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ce764da07ef178a848efd6f305f402cf90d70dd","datavalue":{"value":{"entity-type":"item","numeric-id":4831483,"id":"Q4831483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9a4e07cb4072719f33cc866609ffe166c2c9a40","datavalue":{"value":{"amount":"+0.8355609","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":"Q790804$E439DF29-07EE-4155-9C56-FF61977BADAA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:790804","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:790804"}}}}}