{"entities":{"Q1190984":{"pageid":1201733,"ns":120,"title":"Item:Q1190984","lastrevid":69856947,"modified":"2026-04-13T10:48:42Z","type":"item","id":"Q1190984","labels":{"en":{"language":"en","value":"On the theory of average case complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 58806"}},"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":"Q1190984$96EEAEBF-90D6-4325-9376-9874AB136ED4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6c32e5f6f8964e7eea0e2f990fa910b1e93836fe","datavalue":{"value":{"text":"On the theory of average case complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1190984$58BE9995-9213-4656-820B-D1FE925F6E07","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"909189d67960f4e54f2a96bf66970ec979b0696b","datavalue":{"value":"0762.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190984$70B27125-60DB-402A-8D8D-E88E61A70A42","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ba62dc61a28e1aaa7bda943dcd8097dcf938d700","datavalue":{"value":"10.1016/0022-0000(92)90019-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190984$D719B2D4-9786-46D5-ACE0-7E17A366DD8E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f5e58e6387448cc0a984abcf819b863ae2c2e93","datavalue":{"value":{"entity-type":"item","numeric-id":1009295,"id":"Q1009295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$96787B57-3DAE-4B82-A5F5-22C6BAA96D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"37a920be255189c1a4deaad2b6d6c019df73af95","datavalue":{"value":{"entity-type":"item","numeric-id":582081,"id":"Q582081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$416FF07A-4AA6-4C61-A17E-6479C827ECBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cecf1ef8f97c75d3f636331253c64cfc37610336","datavalue":{"value":{"entity-type":"item","numeric-id":178474,"id":"Q178474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$EB9A7821-A507-4464-8CAC-3A0AE9A0EF9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac4568d84b771eeebbddc71eddb75d7d7a65fc32","datavalue":{"value":{"entity-type":"item","numeric-id":1190983,"id":"Q1190983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$31E58204-8727-413C-AF8D-B8D278959D76","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":"Q1190984$5E432001-5995-4B6A-A715-CD8817941FDA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1190984$67006753-F94F-4294-BA64-9FDCDA68E852","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ecdcbffa68460657b1750519b5fae42bb14fb405","datavalue":{"value":"The paper takes the next step in developing the theory of average case complexity initiated by L . A. Levin. A distributional decision problem is a pair \\((D,\\mu)\\) where \\(D\\) is the set of strings and \\(\\mu\\) is a (distribution) function from strings to the unit interval \\([0,1]\\). Most of the work deals with the class \\(DistNP\\) which consists of all problems (\\(D,\\mu)\\) where \\(D\\in NP\\) and \\(\\mu\\) is computable in polynomial time. A distributional problem \\((D,\\mu)\\) is an Average-\\(P\\) if there exists an algorithm \\(A\\) solving \\(D\\), so that the running time \\(t_ A(x)\\) of \\(A\\) is polynomial on the average with respect to the distribution \\(\\mu\\). This last condition means that  \\[ \\sum_{x\\in\\{0,1\\}:*}t_ A(x):\\epsilon \\cdot \\mu(x)-\\mu(x')/x<\\infty \\]  for some constant \\(\\varepsilon > 0\\), where \\(x'\\) is the immediate predecessor of the string \\(x\\). It is not clear whether \\(DistNP\\subseteq Average-P\\) (even if \\(P\\neq NP\\)). The authors show that this question is related to a classical one in worst case complexity: it is proved that \\(DistNP\\subseteq Average-P\\) implies \\(NTime(2:0(n))=DTime(2:0(n))\\). It is also proved that if \\(DistNP\\) is not contained in Average-\\(P\\) then there exists a problem in \\(DistNP\\) which is neither complete for \\(DistNP\\) nor easy on the average. In fact, it is shown that classical results about the richness of the structure of \\(NP\\) (under polynomial reductions) can be translated to the distributional context (under ``average polynomial'' reductions).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190984$B898B864-7FB6-4EBE-854D-539B6359A3AA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190984$A20F1330-EC3D-476C-888D-D49218A4C58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190984$7FD2A608-6F5B-488F-A695-221725F7059B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"47ce20087ce6b6f15ac61bc111c61a4e93d11fb3","datavalue":{"value":"58806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190984$E86482C4-4B43-43E1-B02C-2C62E75E4458","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de6e6ec99e87a64046813cb3b5f6f74ec4a4a7b2","datavalue":{"value":"average case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190984$E92ED5C6-B888-4853-B3C0-143309933C22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1017bdd4b9b5a08a59a88c6d60d7e1b1f8c0be82","datavalue":{"value":"distributional decision problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190984$6CFBB433-F6EC-4969-802D-820A2493E50D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1833d190eb6492ca84e0c93a6ff12de5694705d3","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$AC8A76F0-86C1-4166-B412-AC065A5B5F63","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":"Q1190984$93E331AD-36EA-4065-82C1-83138B9859A0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c847610ade77b047e3075d35766cbb1d381ec23","datavalue":{"value":{"entity-type":"item","numeric-id":1259907,"id":"Q1259907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$40A349E1-55EA-4B91-B62B-6CC35BB0988D","rank":"normal"},{"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":"Q1190984$7B1DF3AE-F17C-42B6-BE82-5E97DD56FA84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$D836B304-C4E2-4794-9715-DF98E67F420A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42c8b5e50018a3a3ffa751afce659c2a748ea7ec","datavalue":{"value":{"entity-type":"item","numeric-id":3033752,"id":"Q3033752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$E60D345E-3285-4ECF-8124-D93904E37AB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3bbd7d322650d746c71c732cf992db41446ed3a","datavalue":{"value":{"entity-type":"item","numeric-id":3972530,"id":"Q3972530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$47AE0D11-6580-4111-902E-CD8E08F47EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa1d04a268315dc7522d5fb315ded3f152612974","datavalue":{"value":{"entity-type":"item","numeric-id":5896419,"id":"Q5896419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$66092FE3-D45D-418E-9397-BDF2FD7292E8","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":"Q1190984$8AB9CBB4-82E7-407A-A973-D4F5D1BDC573","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69b122dccee1ddb4cd4eb25b91115a7fe50fe6a0","datavalue":{"value":{"entity-type":"item","numeric-id":4173215,"id":"Q4173215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$AF6E6B6A-9823-4238-983B-4707CC910901","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":"Q1190984$069BB224-95FF-4A3B-9A78-4F58F64CC588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"704b67c0c7a5a44ff323d18e1363803acffd4565","datavalue":{"value":{"entity-type":"item","numeric-id":4071737,"id":"Q4071737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$AA7171CD-C4B9-4BF5-A3ED-6E0B010E7893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04533b5e4f54e7a61c4fc1c55a4a47c19e20f43a","datavalue":{"value":{"entity-type":"item","numeric-id":3718151,"id":"Q3718151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$27BDA860-3F1D-48AB-A8D8-EA3226A39562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18b1eff86e275eabe1de48fbbe338962260427bd","datavalue":{"value":{"entity-type":"item","numeric-id":1100894,"id":"Q1100894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$3AAA2C69-DE40-42D9-8472-C63D5E52AA34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$13080E31-E982-46E3-BEDE-40BC76AEAAEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190984$BDF0392C-2205-4F1D-BB62-ACE9C5A3961C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"37a372e39b3910141dd6d84067e5bb17ee2b810b","datavalue":{"value":"https://doi.org/10.1016/0022-0000(92)90019-f","type":"string"},"datatype":"url"},"type":"statement","id":"Q1190984$15E2FBEA-AB89-4E9C-9C95-6E6D2B36EF8B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"28063183765b25ce38952079501a02241bad2366","datavalue":{"value":"W2173249896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190984$55E20F56-AEB0-48A0-8CE2-3252AB6036A0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c16d16f5658aa39d9dbe6d3d6e450ef918143ffc","datavalue":{"value":{"entity-type":"item","numeric-id":4281492,"id":"Q4281492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f71503e3684b6182e251ad1dc5fe4b5ad5d4117","datavalue":{"value":{"amount":"+0.9099457263946532","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":"Q1190984$F0FC2462-13ED-4927-BBB3-512C7AB07124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54254a285e825cd4b7f4d25c73c6088f85d8abc4","datavalue":{"value":{"entity-type":"item","numeric-id":4281567,"id":"Q4281567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8d2b0abef7270c04754222710f8a8394e7a36bd","datavalue":{"value":{"amount":"+0.9096515774726868","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":"Q1190984$2C7B006C-3FDA-4DFF-B14F-95D3F9284152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b3d87c217443bfa0282780a97ff94e4d17c2e71","datavalue":{"value":{"entity-type":"item","numeric-id":3413362,"id":"Q3413362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4299dd2e90d305fe959f4afcd268718f6bd0f46c","datavalue":{"value":{"amount":"+0.8982823491096497","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":"Q1190984$48FCDDE3-0885-4935-8A63-3CE51DC74F37","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the theory of average case complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_theory_of_average_case_complexity"}}}}}