{"entities":{"Q1070822":{"pageid":1081574,"ns":120,"title":"Item:Q1070822","lastrevid":66782364,"modified":"2026-04-12T12:49:59Z","type":"item","id":"Q1070822","labels":{"en":{"language":"en","value":"Some hierarchies of relativized time-bounded complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3938570"}},"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":"Q1070822$5804563D-3327-48A1-BC1A-FE200D7D8B50","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"25df2e4dd484b3c80e0dd0c835362bb062beac6d","datavalue":{"value":{"text":"Some hierarchies of relativized time-bounded complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1070822$8772EE3B-71CB-44AF-9235-31FC31DBD0C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"761bced53219f1b064f27518bff6bf14829830ff","datavalue":{"value":"0585.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070822$B9A3C2CC-38A2-4743-889C-6ABA6B799BEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"583d24e284459bd2669b49dfb361002c7c90b694","datavalue":{"value":{"entity-type":"item","numeric-id":988328,"id":"Q988328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070822$32749623-7A12-4785-9F2C-B584DCAA851D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e32cce6a0fe16100c89e9959909512a93fb24ed2","datavalue":{"value":{"entity-type":"item","numeric-id":1070821,"id":"Q1070821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070822$A13586B3-3AA9-4AC6-89C1-0A2D695BDB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41273bffcfc4219b4cffe4a47dbb26902f1652c3","datavalue":{"value":{"entity-type":"item","numeric-id":917471,"id":"Q917471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070822$D84E1558-13E7-421C-AD72-F3169B739256","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c56c33ef3e883cbe56a171d93462893c540cb008","datavalue":{"value":{"entity-type":"item","numeric-id":174692,"id":"Q174692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070822$AC633BA0-2EDD-4F0D-AAE8-828215499580","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1070822$E31DD43F-01DC-4F8A-8FC2-EF89A9B5B51A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"38452b05bbc06b565fb185532e4da4181b69f54b","datavalue":{"value":"Summary: Some results on relativized time-bounded complexity classes are presented. There can be many kinds of hierarchies of complexity subclasses of relativized NP. For brevity, let P(A,k) [NP(A,k)] be the relativized complexity class \\(DTIME^ A(n^ k)\\) [resp. \\(NTIME^ A(n^ k)]\\) with respect to oracle set A. (For \\(k=1\\), replace \\(n^ k\\) by 2n). Then for example: 1) There is an oracle set A such that for all \\(k>0\\) P(A,k) is properly contained in NP(A,k) and NP(A,k) is properly contained in \\(P(A,k+1)\\). 2) For each \\(k>0\\), there is an oracle set D (depending on k) such that for any \\(i\\leq k\\) P(D,i)\\(\\neq NP(D,i)\\) but for all \\(j>k\\) \\(P(D,j)=NP(D,j)\\). Besides, we show a theorem which is a higher level analog to a theorem of \\textit{R. V. Book}, \\textit{C. B. Wilson} and \\textit{Xu Mei-Rui} [SIAM J. Comput. 11, 571-581 (1982; Zbl 0487.68038)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070822$C145EF2B-487D-410A-99D9-734684D76B71","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070822$286655F6-619C-4662-B945-0977FB49150A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"37763dfef4660581d57f4091920248dc7b1b2b50","datavalue":{"value":"3938570","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070822$800D4873-58DF-42F3-B183-F4EEBC880868","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf40df0cbd0c8ffded73d832fce8830c842552e8","datavalue":{"value":"complexity subclasses of relativized NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070822$DF5FB7F3-A75A-4852-AC9E-AAD71AAF9D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bdb4bf39d306d91ea5536ae58e0b1e3710ac56","datavalue":{"value":"oracle set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070822$FB056355-9383-4CFC-A0EE-D4A3945E2291","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":"Q1070822$2B88D178-F8D9-46B8-BAD2-1891B1EFD2ED","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9728a1c126103fbf0a2f706a928952e06a5eea85","datavalue":{"value":"https://doi.org/10.2977/prims/1195179054","type":"string"},"datatype":"url"},"type":"statement","id":"Q1070822$01D426A0-C50F-4481-81D1-BA156EC580B2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ef9cbd3bd6efeb1afe8305f44e4d0337e80cc39d","datavalue":{"value":"W2065770175","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070822$2A6D7C90-DBE4-4E10-8508-8A6536B3C713","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"12dfd2782214de8254fa1bcb9fdd05e4fe900048","datavalue":{"value":"10.2977/PRIMS/1195179054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070822$17697019-796D-4343-9BDF-79B7F9408929","rank":"normal"}],"P1643":[{"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":"5ed8667e2c4485e56f11ecd3ca66e78814a6b61a","datavalue":{"value":{"amount":"+0.8479690551757812","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":"Q1070822$4D0A48DD-E56E-4305-B2B2-D7D6DA52451A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f03620465fe12ccaa024596240620d9be60a2953","datavalue":{"value":{"entity-type":"item","numeric-id":3347297,"id":"Q3347297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ff68ebb7ac0e0f1b841f88052af61b54120a4e8","datavalue":{"value":{"amount":"+0.832974374294281","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":"Q1070822$80B2386B-3956-4C0B-A1DF-9AABD25C8915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6b96b63dadabe23b457491266261e729df779f3","datavalue":{"value":{"entity-type":"item","numeric-id":3727389,"id":"Q3727389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37d17ce2ff29104af1784251a62ff15e49aa80e1","datavalue":{"value":{"amount":"+0.8267772197723389","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":"Q1070822$97DF87B5-A9E0-4EA1-9667-CA87A5E0504E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a27429ad297dd1a69b539d8ba69ceab17f4c9d7b","datavalue":{"value":{"entity-type":"item","numeric-id":4205078,"id":"Q4205078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"222c8a96da847e7ddc6dbb237e7e39452348fed6","datavalue":{"value":{"amount":"+0.8176449537277222","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":"Q1070822$7C8CEEA3-9FD8-49E1-85F2-3033F8936159","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34db3e8b62604b8fdcd714b654440592bd493ac3","datavalue":{"value":{"entity-type":"item","numeric-id":3675521,"id":"Q3675521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5162a8c0a4d3ec563ab9b754f69654f1ca09b6c3","datavalue":{"value":{"amount":"+0.8147408962249756","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":"Q1070822$E0B74862-6DCC-4A0D-A29E-F1E9E0FCA8C9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some hierarchies of relativized time-bounded complexity classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_hierarchies_of_relativized_time-bounded_complexity_classes"}}}}}