{"entities":{"Q4351919":{"pageid":6381518,"ns":120,"title":"Item:Q4351919","lastrevid":41817058,"modified":"2025-05-08T16:49:33Z","type":"item","id":"Q4351919","labels":{"en":{"language":"en","value":"On Nondeterminism, Enumeration Reducibility and Polynomial Bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1054284"}},"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":"Q4351919$B23D98EE-B2C7-4462-BA34-C7E3B2BCE024","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4757f905a7c9a0151b81488004ff2c60b1b1ca7","datavalue":{"value":{"text":"On Nondeterminism, Enumeration Reducibility and Polynomial Bounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4351919$49FDF93D-A7C9-4764-8ACF-832C308693EE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"040006652744faee4164092b93ba4b9fece82250","datavalue":{"value":"0882.03042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$9B229AC6-FA71-48A3-829A-89864F1A9E87","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"15107e76f5da2d158c87b870794936be3ca49fdb","datavalue":{"value":{"entity-type":"item","numeric-id":3813805,"id":"Q3813805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4351919$A1AE5877-22EF-422B-98B7-9D14D9D1C60C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7af1100b7fbaa31e618c4d49342e2fae8da143f3","datavalue":{"value":{"entity-type":"item","numeric-id":2793901,"id":"Q2793901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4351919$B4B393CD-635E-443D-9B29-2A59E142A223","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1c0636d1f8183c1e3e3dfb36c3e7a25a96aaad60","datavalue":{"value":{"time":"+1997-10-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4351919$9F14C789-C9A7-4936-AE69-CB8A36606194","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$FAB930FE-6F57-447E-A6E1-BB5A00BB5B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$70896B00-5168-4F41-8FFF-CC90FAEC8BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$EA840620-777F-4DA8-81B9-C9933E2D94F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$18472D21-644D-45C5-BD2D-C7EE623F72AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$1FF8304D-2141-4C88-B16E-B3B87EE2B07A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$D4D923E6-3F5F-40BA-B34A-02919BF7D6F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"515d9d870d19a9381b91aa5b92eb5c7fe57062fb","datavalue":{"value":"1054284","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$190FD484-0E4C-4500-B976-3446711F880A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$67EF9EBB-725E-42C6-A951-6E1E4519883D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80c8522115fb624ea4d8f7607da137c6b9d5dc0e","datavalue":{"value":"relative computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$A381639B-4106-481E-BA2B-AA0BF678A762","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f165bf28b50cacc658818bcc911ae4a36222f512","datavalue":{"value":"enumeration reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$E04BFD8D-F3D3-458D-B037-7F8127B42290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba63a3ec360bdcb3035a87816aa2f07e91aebfb4","datavalue":{"value":"enumeration degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$6FA44173-50EB-4005-979F-145B2883A602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16b273759b98cedcfe6d346efa94fac26baf4a98","datavalue":{"value":"polynomial time reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$9074CBE0-4D20-495B-B8DC-F33B9985FC2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6785d636b42c9b81735e7a25676178ab46ee11c","datavalue":{"value":"polynomial time degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$555C39C7-BD71-4883-87E4-27B766F4CF9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7bf3602697cf849530e27ea91c7d4574ce90c0c","datavalue":{"value":"polynomial enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$36A1C81C-CEEC-42BB-AF14-B43F7B99F33E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7c7fdcad96e6c6c6697eb73433ef989fe43b542","datavalue":{"value":"conjunctive reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$2A2A8586-9772-44B4-8F11-EBD65D17E6C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8d9274cbab44b30312fd22862d18c60a30b38ca","datavalue":{"value":"recursive sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$381C53A4-CC3C-4214-B4F0-A2D3FB661284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"004c0885519fc9d672dac6f7a08f4a1925ea562a","datavalue":{"value":"computable sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$2666EE9F-56D7-4FBE-9C76-E025B398AA59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1eecd69a6d6f7ca8849068cc67a56effa10cb344","datavalue":{"value":"minimal pairs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$55DF9E77-5B10-4F24-8699-EADAAC9083C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0249355a8cdf1f888808e13250c420c84fb4c63f","datavalue":{"value":"jump operator","type":"string"},"datatype":"string"},"type":"statement","id":"Q4351919$7A728D03-8910-4EC7-8728-788C152EE1D1","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":"Q4351919$6E61BB3D-4791-4C2D-BB3E-339AAEE16F3B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1aa968a12c03e8d12f5ad845c68d9bdaa8488be0","datavalue":{"value":"https://doi.org/10.1002/malq.19970430302","type":"string"},"datatype":"url"},"type":"statement","id":"Q4351919$1AC215D0-02B8-4331-A282-8E0411E4E442","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1a1b854d88b39d188931ded6959d312b41784835","datavalue":{"value":"W1984891917","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$09E39DD1-FA16-4BA6-8CB5-B9AF0602174B","rank":"normal"}],"P223":[{"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":"Q4351919$38CE0DE6-CC31-41E5-BA19-7CB73A6F66C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4351919$092A3C74-CD01-450A-834D-53AA3AD2125D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"40b1c17b653fcf692624dcd1492936867cf343b2","datavalue":{"value":"10.1002/MALQ.19970430302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4351919$F252C12B-468C-46BD-A4F3-C26F80DB314A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af93c3518d52b27300474ef3cda93d68af99966a","datavalue":{"value":{"entity-type":"item","numeric-id":3487329,"id":"Q3487329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ec2579b3e4a7352d96d43d3b6e4939bbe14c234","datavalue":{"value":{"amount":"+0.9212501","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":"Q4351919$AF4EBDF3-6923-4BBF-83A3-114C33BD6719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82b86d9964b01e2a3a2ac0b2bde680fe46b545be","datavalue":{"value":{"entity-type":"item","numeric-id":4259986,"id":"Q4259986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bffe4ba522e5e884ddf4eb68a7094ed3638fee2","datavalue":{"value":{"amount":"+0.9204198","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":"Q4351919$FD65C3D0-6078-4046-9C23-EAA46C5676F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76a04e98538daca0829573c46959063d1115fe13","datavalue":{"value":{"entity-type":"item","numeric-id":5898819,"id":"Q5898819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0874815943eb41268140f6e2070cd7092ff8168","datavalue":{"value":{"amount":"+0.9159025","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":"Q4351919$91367AC3-B222-45B5-8E85-162B26265904","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":"1071d8f1da390f08c840bf417d1ca9ca2449945e","datavalue":{"value":{"amount":"+0.9141655","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":"Q4351919$EB7E771F-8207-4508-B407-D530E441506A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a890c50bbd6fe34f04c8b0ebd86493e15217975","datavalue":{"value":{"entity-type":"item","numeric-id":3033754,"id":"Q3033754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c1bd6abb930239a8c3c19a6d12029746225cb1a","datavalue":{"value":{"amount":"+0.90516204","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":"Q4351919$1475C576-8DD1-4938-B92E-53308F5B9D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfee4e001601e340d50b91ff0d09a5de7469fb13","datavalue":{"value":{"entity-type":"item","numeric-id":1201882,"id":"Q1201882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1d1c4816401552af3d55c52f1cf291071405283","datavalue":{"value":{"amount":"+0.90334034","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":"Q4351919$5B64B26A-9428-46DD-A92F-D64B9D81300B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"083178c9294c47177c81e04231c28dc8ce6c6987","datavalue":{"value":{"entity-type":"item","numeric-id":2970965,"id":"Q2970965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8377325fd4928c1a8595a57324180088985b1181","datavalue":{"value":{"amount":"+0.89442456","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":"Q4351919$08849F3B-EF35-4A8A-854A-EEF8C0AE2E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9a4a9e9f5e8aa25df337aefed053db314f25aba","datavalue":{"value":{"entity-type":"item","numeric-id":4723714,"id":"Q4723714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0aae7be57e1baddf10f8b24a15c87d73607df81","datavalue":{"value":{"amount":"+0.894394","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":"Q4351919$0939FD9A-4D0E-47F4-8C58-714FF03D370E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b5d6ef5c15291d9ea7bc547c0ce0b30e8c762fa","datavalue":{"value":{"entity-type":"item","numeric-id":5951067,"id":"Q5951067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"777b6c8b90751a775ad2812d05df44f34a07a0f4","datavalue":{"value":{"amount":"+0.893665","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":"Q4351919$46C11777-06E0-4BB1-8BB5-E60260E0B4C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ce7b7a8dcb11cf09a97ce39fb74733473796256","datavalue":{"value":{"entity-type":"item","numeric-id":2179352,"id":"Q2179352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"490697499e8aa941f677db1ab08d3d649cca0156","datavalue":{"value":{"amount":"+0.8867879","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":"Q4351919$F7B5AD6F-7C66-4EC6-B2AF-350B65671D91","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4351919","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4351919"}}}}}