{"entities":{"Q391074":{"pageid":392841,"ns":120,"title":"Item:Q391074","lastrevid":61569453,"modified":"2026-04-11T00:12:22Z","type":"item","id":"Q391074","labels":{"en":{"language":"en","value":"Nontriviality for exponential time w.r.t. weak reducibilities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6244004"}},"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":"Q391074$25C47828-99C1-4CB8-AC5D-B0634C95B1B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"85781a5abeef93440e8d900ba680d17a6071db8f","datavalue":{"value":{"text":"Nontriviality for exponential time w.r.t. weak reducibilities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q391074$3193327D-2CF5-4EB1-9077-D6444E7D6E0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"62ac060e613287b6c847dc5faf14f399b10c0a1f","datavalue":{"value":"1294.68082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391074$EC676E32-3EA5-49E5-8FF2-F1668BFF65E5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"320a984166f56a9a37c4770d3305636d51ad7408","datavalue":{"value":{"entity-type":"item","numeric-id":391073,"id":"Q391073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$4161D486-8AF2-44DE-B49C-BDF6847BF4D3","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":"Q391074$60C06B31-E1CA-435B-957F-06F2FA188136","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":"Q391074$883E1B06-38EA-46D5-A172-DAD796EE384D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2c704b287c68a3d4d8361a025642d6eba13574eb","datavalue":{"value":{"time":"+2014-01-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q391074$7475A838-BA6C-4295-9102-4E9AFBFFC642","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391074$1B1139D5-287C-4280-83DD-EA9BD4E3814B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391074$94A96687-B71A-4A75-8A0C-5B36547015DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"60f333fba54a53b8eb0e956265d45e69ec8438f3","datavalue":{"value":"6244004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391074$75CE4656-DDC4-4DC2-B8A3-9FD8E8FE29AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eda9f60512d8e02150a46e43e911af2e47469421","datavalue":{"value":"bounded truth-table reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q391074$9E501A74-053D-487B-95B7-F9E0A896C699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"500ee7e0a7d2f3bbb446b88103245bcad76bcc62","datavalue":{"value":"polynomial exponential hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q391074$782ABD02-CC01-4CAB-9D8D-1624DD28A716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca8747e792c9ec070a2b651f7745015b1625753b","datavalue":{"value":"Turing reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q391074$271F2E31-0489-483A-B680-2963F73D13F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"214cfd74473bc6d0eae3b8ca28189646d43fd7f1","datavalue":{"value":"many-one reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q391074$0B7C8FC0-D744-4F01-9516-11097A935A13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d4e15085277c77e1f6537f1355f78224cb0f64","datavalue":{"value":"truth-table reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q391074$1220EE87-4126-4FCB-9858-D14F77B27974","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":"Q391074$500B6ACA-C442-4FFF-8033-A448AD7EEBB4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f36637668c9fb21cb866cfc5b48ea7201c4a379a","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2012.05.022","type":"string"},"datatype":"url"},"type":"statement","id":"Q391074$2F064B33-7049-45B6-A233-8E71B1051DEC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5101fb2783cb0805bd3a2b46213824b545683391","datavalue":{"value":"W2139429469","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391074$BA949946-BCB7-4F24-8CCF-942447B7A27F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"49b16bb492e6fd933d5b5c7ba87f5c046475dfe7","datavalue":{"value":{"entity-type":"item","numeric-id":3569066,"id":"Q3569066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$02A49AC3-B09A-4972-8A1C-C7DF0ED9F20F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5700e6285d53ea42fdce5371a6765818e425aea6","datavalue":{"value":{"entity-type":"item","numeric-id":3587403,"id":"Q3587403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$BAC44D72-C7CC-4889-8451-8D79EB7309B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04aaaaf5322a06552a89ba77168c1fdf61a32d09","datavalue":{"value":{"entity-type":"item","numeric-id":693048,"id":"Q693048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$E74D85A6-736A-4683-ABF7-2FE6DBD6F3C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e0a936d29cdb004405e9ceab9ae0698c1fa987d","datavalue":{"value":{"entity-type":"item","numeric-id":4321931,"id":"Q4321931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$DED3037E-8123-4B51-95FC-7FC78A9BFFA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cfc53db72d247da5f30e677d4e958d296619aa4","datavalue":{"value":{"entity-type":"item","numeric-id":3996675,"id":"Q3996675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$AA835A18-803F-416A-8D1F-1867D5D0198F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d74fa837cf60958bc78986acc4d8d4832c3ef5e","datavalue":{"value":{"entity-type":"item","numeric-id":1261477,"id":"Q1261477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$59E5FFC8-36C7-4093-9477-96C7DEE327D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f754f760d683b9eb73d4cd49ce866cf1da65ebe","datavalue":{"value":{"entity-type":"item","numeric-id":673644,"id":"Q673644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$03E2FFCE-D665-4AED-B798-C0D6921A043A","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":"Q391074$ABA95C25-CC07-4821-92B5-88523D15D27F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a1e48c9a5008f1a77fabcc79524858a40009c63","datavalue":{"value":{"entity-type":"item","numeric-id":4862792,"id":"Q4862792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$340A7271-8789-4041-A360-2B79850E62D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2287ea70716fc40f2d1ac564c031496968b69b1","datavalue":{"value":{"entity-type":"item","numeric-id":1097692,"id":"Q1097692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391074$5D476615-4D16-4932-91A9-5EC49A68E066","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"407be46b3bf20d6ad2d96f9b07c59cb8f37a562a","datavalue":{"value":"10.1016/J.TCS.2012.05.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391074$D6150DDE-6833-4861-AB4F-AC52504E9513","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0482375f99e0900dbe6439d1c2105c0ed8e1f14a","datavalue":{"value":{"entity-type":"item","numeric-id":3569066,"id":"Q3569066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed0d4a8002d98ae475e924c65685a1d36c2409a","datavalue":{"value":{"amount":"+1.0000001","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":"Q391074$35B5F41A-2A3D-43D6-9D85-1020BA69F806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41edc5a236d1b7a28cbd6c5831bcacc0892bb515","datavalue":{"value":{"entity-type":"item","numeric-id":2800573,"id":"Q2800573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea3429631906ca7e6e88b8746a6d96f509e868e4","datavalue":{"value":{"amount":"+0.93637735","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":"Q391074$3A95EB02-8B38-46CB-BCE1-03859CD5DE4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e9ebcdf7d03ab55ec53413c3ff8191e5a54d65c","datavalue":{"value":{"entity-type":"item","numeric-id":3587403,"id":"Q3587403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03c3f12786659df0b01146e64514e7784d282cbd","datavalue":{"value":{"amount":"+0.9268802","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":"Q391074$7E82897D-7FA7-4630-9D93-72200F764EF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"896589d1ede5c08d23ad4be5a4deb9cbcfee8266","datavalue":{"value":{"entity-type":"item","numeric-id":2322715,"id":"Q2322715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03c3f12786659df0b01146e64514e7784d282cbd","datavalue":{"value":{"amount":"+0.9268802","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":"Q391074$0D5BB681-7C9D-4062-A378-9A4A885F8243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4536b540288583a034940eeedf78550263f6d49","datavalue":{"value":{"entity-type":"item","numeric-id":4418681,"id":"Q4418681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5b79ffc608b3ea41f59dc9e08b898dadebad497","datavalue":{"value":{"amount":"+0.9006507","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":"Q391074$C90EC7D5-A97E-4607-95C8-9F36ED4740A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8e85e69c97abfeb1a1b7ede13608a12658b9b4a","datavalue":{"value":{"entity-type":"item","numeric-id":4733404,"id":"Q4733404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86d5781db111c7716643313b5667c09e5b5101b0","datavalue":{"value":{"amount":"+0.88282335","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":"Q391074$1E7F0977-4192-49CC-B693-79F74207C884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1242de007368903ff815190b4c5dd3bb7abf7bb7","datavalue":{"value":{"entity-type":"item","numeric-id":909465,"id":"Q909465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78bb6b6b6ffc232edec8ad81fc21a75eebdcbc95","datavalue":{"value":{"amount":"+0.8784723","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":"Q391074$99D7D893-36DF-4750-BBF5-6499B7DD8DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63972a5766fe7e0bf816f6edcf9e8d394a25c4c1","datavalue":{"value":{"entity-type":"item","numeric-id":4359459,"id":"Q4359459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"077a0ffb6386cbe52fd8f8bcb2d8a98f8faac1bf","datavalue":{"value":{"amount":"+0.877411","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":"Q391074$2B098C9D-E673-4940-9C39-753CEC29840A","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":"d674f58293f9cf719f0b1917966e717e392b800a","datavalue":{"value":{"amount":"+0.87413317","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":"Q391074$C8FDB7BC-C50A-4422-AFEE-6A18348FF327","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nontriviality for exponential time w.r.t. weak reducibilities","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nontriviality_for_exponential_time_w.r.t._weak_reducibilities"}}}}}