{"entities":{"Q1107526":{"pageid":1118275,"ns":120,"title":"Item:Q1107526","lastrevid":49198642,"modified":"2026-01-06T18:18:12Z","type":"item","id":"Q1107526","labels":{"en":{"language":"en","value":"Diagonalizations over polynomial time computable sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064976"}},"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":"Q1107526$1935D4C7-9CE7-4B20-B0A8-ACBBFFAB2446","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ddb9c4ced39f8c1576bb4f51ad58e0b2f9592e80","datavalue":{"value":{"text":"Diagonalizations over polynomial time computable sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107526$595445AB-0B61-4D9F-AA3F-2D5BA77739A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"92992510b05b434a994144efcc6f6afe6626c75d","datavalue":{"value":"0653.03028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107526$9B1242EB-6D3A-42CE-B4E0-586CC8A284C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"99de640379c6a653f52e0319e9c6ffd36cc163ac","datavalue":{"value":"10.1016/0304-3975(87)90053-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107526$14D0489E-BB91-4BE2-BDAD-5E39CE743C53","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f8011d84e712e567d2b55d9da9960ba9d6f2fad","datavalue":{"value":{"entity-type":"item","numeric-id":1107525,"id":"Q1107525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$AE79FBEA-1856-4530-8167-A59FBF815508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e210f462fe7725dcece418c503a6a20a74d76c17","datavalue":{"value":{"entity-type":"item","numeric-id":749646,"id":"Q749646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$FA380589-2CC8-47FB-9CD4-2DFD6C766D43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b09a388965329c926d542d4fdd3e9db9fa7e3d1","datavalue":{"value":{"entity-type":"item","numeric-id":162061,"id":"Q162061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$FB506A8A-897A-4623-A5BF-89EFA1B5E0E0","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":"Q1107526$B5AFB677-E840-4B97-B103-C78601334754","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1107526$19C873FE-4BC5-4052-B11E-3B319E4D7642","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"08352eaf63fdf64c3b9726dc37370b6be4054e67","datavalue":{"value":"A formal notion of diagonalization is developed which allows to enforce properties that are related to the class of polynomial time computable sets (the class of polynomial time computable functions respectively), like, e.g., p-immunity. It is shown that there are sets - called p- generic - which have all properties enforceable by such diagonalizations. We study the behaviour and the complexity of p-generic sets. In particular, we show that the existence of p-generic sets in NP is oracle dependent, even if we assume \\(P\\neq NP\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107526$FCEE0B36-D669-4B58-98F7-4771F27273D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107526$39F96B53-648F-441C-95BA-A6E25F0FB3EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107526$D38CDF39-38E1-4F1D-999C-EDC1599243EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107526$8720D41C-6E85-4A8E-B5C6-B9A3DA147DDC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bc6da139d9401967b7feca13c78eb3d5f415b666","datavalue":{"value":"4064976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107526$A10B1B9D-80D0-41D4-9620-9A6BB1B9470A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe482273e305293356e93ecadbd9b1e669ce0e52","datavalue":{"value":"diagonalization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107526$A9130F18-F90F-454B-9C0E-D6CD33FD844C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f732777b93a362b174e06a940f9a10857aa2749d","datavalue":{"value":"polynomial time computable sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107526$3FBCDE0F-0C76-4A00-B815-1D629CE56051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91bd107f92cf006edffcabb17c80bb2fb5b788cb","datavalue":{"value":"polynomial time computable functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107526$7384C40A-B71C-4552-94E4-BCC53178AC71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e629d58e0200fc08dd4a29de0db5daf98a2c885","datavalue":{"value":"p-immunity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107526$1EB330EA-48CC-4A49-BCD7-44CB8A9F4634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91926ccf57e5e95cda22daf88b51dc73f97def75","datavalue":{"value":"p-generic sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107526$1D5D4804-7709-4D11-8234-F532C979C5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834c45d526445b63ede129bf0252d3b47bed13e5","datavalue":{"value":"NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107526$A0E62294-CF5F-4768-8265-5464ACD8BBE5","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":"Q1107526$EF86EEFB-B233-4BF4-A20B-66AA8FC48BDC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"876ccbb4e458ede2bead1661c215375d4e8e8094","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90053-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107526$63727F36-104F-4104-AC63-15F2B12B396E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c2bce9c9f094cfd75c0b4c58adff2a3c85d83efc","datavalue":{"value":"W2004243323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107526$B3AF7588-218F-4253-9201-02273C2AD217","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"32957748cf07ec3a1e720ec7fc8eabd55454b055","datavalue":{"value":{"entity-type":"item","numeric-id":3337457,"id":"Q3337457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$F1D1FF79-909F-4D09-8F25-4C415077976B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"685363eaf4edc3874ecc88f53b629a0bce7ba7bd","datavalue":{"value":{"entity-type":"item","numeric-id":4854879,"id":"Q4854879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$3D694210-C0CF-4B70-B609-2936D182EB81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"362b4d190f72f84402187b8eab690d2254cf40ea","datavalue":{"value":{"entity-type":"item","numeric-id":3220571,"id":"Q3220571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$17875F6C-5F0B-4CF5-9CF8-72855A2B456D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$BC6793F2-C6F2-4AA6-83C5-B8BFA1EEBCFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d83bc67e0da55ee1172a31850c3866e3f80bbb86","datavalue":{"value":{"entity-type":"item","numeric-id":3217603,"id":"Q3217603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$B6A6DFC4-90E7-4C10-AD2E-AE07686533A7","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":"Q1107526$E61AE1E4-676B-46BA-BAC7-3774B09D05B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9af52c66421185c07ca4d865efeb189c0dddc801","datavalue":{"value":{"entity-type":"item","numeric-id":1158964,"id":"Q1158964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$8E9AA845-9FEF-47C7-82B1-5B1B90DA419A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c221c3578fd1d37188ec71aeedab58b4cbb8e415","datavalue":{"value":{"entity-type":"item","numeric-id":3751568,"id":"Q3751568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$4E750A34-2BA6-4D12-BB89-53F53FE1B8BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2bcba6abf24137e5ea317e56b32f617a34d2b1e","datavalue":{"value":{"entity-type":"item","numeric-id":795829,"id":"Q795829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$0E3BA508-FC0F-4847-9FB3-00535D75D290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"748ffe7b0a6f8d85b8dada53039ea75346747b8d","datavalue":{"value":{"entity-type":"item","numeric-id":3724315,"id":"Q3724315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$97E2BF18-F615-42E8-A000-7BEA8EC083F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40c62062de7837e74980976f9ffd2b1553f5599b","datavalue":{"value":{"entity-type":"item","numeric-id":1140080,"id":"Q1140080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$7A159E28-3A64-4171-94D7-4786BEEF22E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$C4EE820D-A5F1-4728-BF2E-79FF5D253012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$135D2806-ACD8-4BC2-BA8A-A95ACA9523AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ece2270b16b9fbc48e0a9ac072c1cea045ecd584","datavalue":{"value":{"entity-type":"item","numeric-id":1162811,"id":"Q1162811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$53E9AC84-C511-4CD8-9BF6-FC750E5E7C56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe67cddb1d2e8d4582eb3ba360c56bb29576a54c","datavalue":{"value":{"entity-type":"item","numeric-id":3329452,"id":"Q3329452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$D8143CB7-C121-443E-8997-95C992D262A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b279482656ec86b6b6891121d4904a1250a8e56","datavalue":{"value":{"entity-type":"item","numeric-id":3962980,"id":"Q3962980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$ECDEC4ED-16E8-4A23-BDA3-BC2C5150F32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cefd7574d6776aa0391d0dd90bd375c1811d3f9","datavalue":{"value":{"entity-type":"item","numeric-id":1164414,"id":"Q1164414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$623AC1AC-FE97-4DF4-9C1D-C5231039193B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37bd93f050a29505d9954e41ab03268b153e49a7","datavalue":{"value":{"entity-type":"item","numeric-id":4190619,"id":"Q4190619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$490F3E8A-96E5-4CFC-802C-BD26B7247FE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1edcfc8f162dce621803913f4363a765362e71d8","datavalue":{"value":{"entity-type":"item","numeric-id":3819052,"id":"Q3819052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107526$A5AC6EB0-8136-4190-A407-B7059AE7B00D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d07c1e73a423948cb10f66f95611db277557c2a0","datavalue":{"value":{"entity-type":"item","numeric-id":3220571,"id":"Q3220571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7c0cc2fd8f6d09c5d30149600a0028bd0794910","datavalue":{"value":{"amount":"+0.9625766277313232","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":"Q1107526$E9AEA74F-F3D2-459E-8F9F-8BD54C1738CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fc3a4dbc0596680ffe76028a27a72b448ca610e","datavalue":{"value":{"entity-type":"item","numeric-id":4734760,"id":"Q4734760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d361ead566e1085d438b389004831b7ba359804","datavalue":{"value":{"amount":"+0.8335174918174744","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":"Q1107526$F3FC22C9-C245-41C5-8D67-81D2DB5F2F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c9ae2680c645aeb19f7983cdf2a97301e255519","datavalue":{"value":{"entity-type":"item","numeric-id":5151221,"id":"Q5151221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73331d384658839fd1bde24e10d03962acdcd8a6","datavalue":{"value":{"amount":"+0.8008450269699097","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":"Q1107526$F275446C-22FD-4293-9AA4-42D6F077AC78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a82e81c3f139999c194d1a6fabd750e988d2908e","datavalue":{"value":{"entity-type":"item","numeric-id":4863237,"id":"Q4863237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ae288f45214a6fd96439d407faac1871d3e521e","datavalue":{"value":{"amount":"+0.777125895023346","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":"Q1107526$DBB8B821-3338-4036-A2D8-46862D08A174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b38698410b10d1b605e95efd4de66bd5ba470a8","datavalue":{"value":{"entity-type":"item","numeric-id":3484825,"id":"Q3484825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ae288f45214a6fd96439d407faac1871d3e521e","datavalue":{"value":{"amount":"+0.777125895023346","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":"Q1107526$E14C08F5-9929-4EEF-AA4A-F578A6DD0A0D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1107526","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1107526"}}}}}