{"entities":{"Q795503":{"pageid":797351,"ns":120,"title":"Item:Q795503","lastrevid":48719695,"modified":"2026-01-05T17:15:49Z","type":"item","id":"Q795503","labels":{"en":{"language":"en","value":"The critical complexity of graph properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3862431"}},"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":"Q795503$B7FC07A6-DC06-4D71-B5B7-25F3CDF8FAD5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b87a9eec0f4352057f8c746afb7abfdce00bb921","datavalue":{"value":{"text":"The critical complexity of graph properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q795503$6CD57B7A-FF62-43A7-A1AF-15C2D02986D7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bbc8657af3316332f4e6c957c9f90ec4bc43990f","datavalue":{"value":"0542.68026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795503$FE93EBF4-69C0-4A28-A47A-0957715D3D5D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b953e051ce844d22d75c633ae0d470370fb57db2","datavalue":{"value":"10.1016/0020-0190(84)90019-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795503$08EEF3B6-2771-4F29-BAC7-DD6CF04ED6CF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c66a437d74ae466cacad614cef92f8e5d71204e6","datavalue":{"value":{"entity-type":"item","numeric-id":239429,"id":"Q239429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795503$37F88C78-5EEA-438A-A6DD-5749AC8348A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795503$C1FE45D3-1D65-456B-8A29-ED5F94120AEB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q795503$E25C260F-0DD4-4B4F-AE0E-7722340CE9FF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e6b60efaae3f0198efd576976c800c29c23781b","datavalue":{"value":"The critical complexity of a Boolean function \\(f(x_ 1,...,x_ n)\\) is \\(c(f):=\\max \\{| \\{i:\\quad f(x)\\neq f(x^ i)\\}|:\\quad x\\in \\{0,1\\}^ n\\},\\) where \\(x^ i\\) is obtained by changing the i-th component of x. \\textit{S. Cook} and \\textit{C. Dwork} [Bounds on the time for parallel RAMs to compute simple functions, Proc. 14th ACM STOC, 231-233 (1982)] proved that log c(f) (in base \\({1\\over2}(5+\\sqrt{21}))\\) is a lower bound to the time needed by a parallel RAM to compute f. \\textit{H.-U. Simon} [Lect. Notes Comput. Sci. 158, 439-444 (1983; Zbl 0523.68036)] gave a sharp \\(\\Omega\\) (log n) bound for the critical complexity of nondegenerate Boolean functions. Here it is shown that if \\(n=\\left( \\begin{matrix} m\\\\ 2\\end{matrix} \\right)\\) and f is a nontrivial property of graphs on m vertices, then \\(c(f)\\geq \\lfloor m/4\\rfloor.\\) (The property of containing an isolated point shows that the bound is sharp within a constant factor.) This implies an \\(\\Omega\\) (log n) lower bound to the parallel complexity of graph properties.","type":"string"},"datatype":"string"},"type":"statement","id":"Q795503$06041508-D074-454F-BBCA-3BD241B0456B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795503$9A387A4E-8568-4B5D-A88A-0EBBC0F23EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795503$A8DA9D4A-8504-458C-BF78-72F487089403","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cc524a72ca56df18d9e52d3dbaf93eda822bbdc6","datavalue":{"value":"3862431","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795503$0A9E8949-A962-452F-AB46-DB893D7A778B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db5e0888fa9957c443e210eb3c88f717e276ae13","datavalue":{"value":"parallel processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q795503$C479B163-AAA4-487B-A59B-FBDA365D808F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13d97924d921957f1fb411623ecca09dfd238e2f","datavalue":{"value":"critical complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q795503$9DF21FA9-FAB9-4C54-AC0F-B660DADCAE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q795503$08F7D4EA-960E-4222-96E7-D6D3F64CA964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f2b3def7b45dec80ef16092f6230f087ef6329b","datavalue":{"value":"parallel complexity of graph properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q795503$2EC13AB7-7259-4360-9FD5-8D0300D8DF24","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":"Q795503$5809094F-89FB-45D3-917E-049D9BD7F812","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be7ec776afc6ad8ad178675a434e62027116713","datavalue":{"value":{"entity-type":"item","numeric-id":1238421,"id":"Q1238421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795503$B400C451-3878-4D69-A9A7-EFF55246D5B6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f3a87f013ecf0bbbf94b016d4d77b816e1836b01","datavalue":{"value":"https://doi.org/10.1016/0020-0190(84)90019-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q795503$80CB0D3A-2DC2-4E25-BB5B-DFB4CBA17413","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99be55acf75401dc7683adf9b7489bc8839737e2","datavalue":{"value":"W2089621728","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795503$916F2220-25ED-4936-8A58-346B18B32F22","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f632c0e3131473761e8bc1cdc0b37e0d043daf1e","datavalue":{"value":{"entity-type":"item","numeric-id":3716300,"id":"Q3716300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afc6b0e9e436de448bdd35ac464932f44703becb","datavalue":{"value":{"amount":"+0.8823091983795166","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":"Q795503$1E7FC6C3-435A-4A8B-9B6D-8254C93B40CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdb024131d358a5e278fcde194f5e5d8b35b5902","datavalue":{"value":{"entity-type":"item","numeric-id":3691584,"id":"Q3691584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84b63c4ea711e2cf61507da838726225b7df8222","datavalue":{"value":{"amount":"+0.8678281903266907","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":"Q795503$DF5D0156-168D-4A23-88C7-D702A5A5E2F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03fa2994c3536a7370be5a046c04743bba99954a","datavalue":{"value":{"entity-type":"item","numeric-id":3419765,"id":"Q3419765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da7141b216e7004b8f0fd53a214ba207a995590f","datavalue":{"value":{"amount":"+0.8162760734558105","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":"Q795503$874902CD-98E9-446D-9D8B-C941D70C43EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0c01298b1f3918107dc40c5e3a97afab7a6a521","datavalue":{"value":{"entity-type":"item","numeric-id":1180407,"id":"Q1180407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ae4152825992d92b2934acf3b6ef46a08161d47","datavalue":{"value":{"amount":"+0.8013505935668945","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":"Q795503$5115FBB3-0622-465D-B581-0D92ED316E5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7643027ac245a0e31431571fc7df9646fb69c4d7","datavalue":{"value":{"entity-type":"item","numeric-id":653841,"id":"Q653841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c159ddf94ef24ac2b8b641e82450cf9b721e9e65","datavalue":{"value":{"amount":"+0.7976918816566467","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":"Q795503$A0D4B88D-6872-4F4D-A5B0-C7AC935AE4B1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:795503","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:795503"}}}}}