{"entities":{"Q942023":{"pageid":943871,"ns":120,"title":"Item:Q942023","lastrevid":65541054,"modified":"2026-04-12T03:18:21Z","type":"item","id":"Q942023","labels":{"en":{"language":"en","value":"On the computational complexity of the Riemann mapping"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5319817"}},"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":"Q942023$600F9486-40F7-4B91-8163-D11C1189FC27","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"109e1034d64e9ce7379bf4b1045f359fe4288e62","datavalue":{"value":{"text":"On the computational complexity of the Riemann mapping","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q942023$54B34035-B057-41FB-BCB1-B34DC15B46DB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2f21956efcad04d61f15233e6f70d118a92da11","datavalue":{"value":"1153.30005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$51C47665-B041-4B26-973D-CC82E5684E19","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6669a82ef13829f14b28c1e93a0ab132a9ddb60a","datavalue":{"value":{"entity-type":"item","numeric-id":343865,"id":"Q343865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$8FAF3B23-8696-4CE8-9FAC-4630372D9E9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e483a89a58087ad020fa302da092f016270f05a","datavalue":{"value":{"entity-type":"item","numeric-id":196251,"id":"Q196251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$DFBD24EB-7CFA-45FA-AD89-C06F17916736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"79e6de294054244913fcd6142c5e40bf072fab79","datavalue":{"value":{"entity-type":"item","numeric-id":982705,"id":"Q982705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$3F6566C8-1CCF-4C88-9561-EB8254F00F20","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"13570f52327b6d519b5e78582bddbe55f7464260","datavalue":{"value":{"entity-type":"item","numeric-id":283965,"id":"Q283965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$DC3480B9-7548-463D-9823-1A29F45EDE82","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c2a5d52678821df208ba2c90770479fded203029","datavalue":{"value":{"time":"+2008-09-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q942023$18958D3C-C527-4D69-B8D9-B31C268C8C9F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"36b204829cdfd8d34bc8ec6d802d4cd017216837","datavalue":{"value":"https://arxiv.org/abs/math/0505617","type":"string"},"datatype":"url"},"type":"statement","id":"Q942023$02A4981D-76F7-4CE9-90C0-61385BA54B98","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa516b6598ec140a17cb2e044d7e4f69d08fdd91","datavalue":{"value":"The paper is devoted to the theoretical foundations of numerically approximating the Riemann conformal mapping of a domain \\(\\Omega\\) onto the unit disk \\(\\mathbb D\\). The authors propose a new algorithm for computing the Riemann map using the random walks solution to the general Dirichlet problem to solve the uniformization problem. The computational complexity depends on how the boundary of the computable uniformized domain \\(\\Omega\\) is specified. The approximation of the boundary is given either as a list of pixels or by a Turing machine. In both settings nontrivial upper and lower bounds are obtained. The general formulations assume that the algorithm will have an access to an oracle for the computing function.   In the scale where the entire boundary is given explicitly, and not by an oracle for it, the result is stated in Theorem 1.11: There is an algorithm \\(A'\\) that computes the uniformizing map in the following sense. Let \\(\\Omega\\) be a bounded simply connected domain, and \\(w_0\\in\\Omega\\). Suppose that for some \\(n=2^k\\), \\(\\partial\\Omega\\) is given to \\(A'\\) with precision \\(1/n\\) by \\(O(n^2)\\) pixels. Then \\(A'\\) computes the absolute values of the uniformizing map \\(\\phi: (\\Omega,w_0)\\to(\\mathbb D,0)\\) within an error of \\(O(1/n)\\) in randomized space bounded by \\(O(k)\\) and time polynomial in \\(n=2^k\\) (that is, by a BPL(n)-machine). Furthermore, the algorithm computes the value of \\(\\phi(w)\\) with precision \\(1/n\\) as long as \\(| \\phi(w)| <1-1/n\\).  The complexity of the uniformization can be quite high, even to compute the conformal radius of \\(\\Omega\\). The corresponding theorems describe the computational complexity of this problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q942023$6A21505C-4E37-4987-B650-F2E399A5E8CC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3d3dc035638a9d6fcb7908dfbb10e85aa32ef59c","datavalue":{"value":"30C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$ADB55F02-445B-4DEB-8360-092C4537733A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$2B7C43BB-A51B-4EB6-BF91-9057CB4921F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$63EC21B9-046B-4158-9E1C-7A6146145934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$6703AB8F-21E0-4926-91ED-8AB171E45613","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5ab61add6329fe3dc334547237f6e1d80b834f1e","datavalue":{"value":"5319817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$A2A1B5BA-A5FA-41D3-9E69-E536F30C871A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q942023$AE2F4802-F1AD-4440-ADEA-993410EA4A29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bcb7f0a5ce31a145a44508f674534483e299ae6","datavalue":{"value":"Riemann mapping","type":"string"},"datatype":"string"},"type":"statement","id":"Q942023$00D7A65B-5978-44B7-AC55-310C9D954155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90fad02fec91ba3292e787175ff739e6bc5650fb","datavalue":{"value":"Dirichlet problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q942023$9BC432EA-35F6-4503-9E51-C2BF9437475E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q942023$3CCDE489-937B-4A0C-8CA9-502CEB171003","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b2b5848d6e6ba7e3851dad0ec1bf7c59cbebfba8","datavalue":{"value":{"entity-type":"item","numeric-id":634822,"id":"Q634822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$63FBE7D7-F8A4-4B8A-8B67-2014D4622D23","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":"Q942023$9D753686-EADD-4AFE-B52A-F3B1335F5244","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"463fe14cee9ef6c22528ef8bab9b1268088ee204","datavalue":{"value":"W2092096082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$819F9482-3C7B-4430-9E4E-8AB7E7CFDFC2","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"68772c3ee7debd9c855d480a01e47282f616c1f3","datavalue":{"value":"Q56060666","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$9BE7AAB7-9911-4188-A026-C3221BB22967","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02ebf0568f47635f182c488d881f7744ddea83e","datavalue":{"value":{"entity-type":"item","numeric-id":3803111,"id":"Q3803111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$D3FCD11C-BA67-430B-8166-A65D7093F0F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab3169539cbe11c3f3329a40e2d9b9929885895f","datavalue":{"value":{"entity-type":"item","numeric-id":1292398,"id":"Q1292398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$1180CFFA-E591-4ACA-8D2F-870D4FE5F138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"144371fb79c01c6df48b1e608243e247572e855e","datavalue":{"value":{"entity-type":"item","numeric-id":2557342,"id":"Q2557342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$3974C662-B52C-49DA-AC16-6439D272ABB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9f98aa6f137610047350615831ea1be3ce70f29","datavalue":{"value":{"entity-type":"item","numeric-id":3660033,"id":"Q3660033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$316909AD-536B-4570-BC1D-35582827CBCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$0B813875-310D-49A7-A7CA-937FD813D9B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31e8504f09d6def02674d1c7dd39ac61be319e99","datavalue":{"value":{"entity-type":"item","numeric-id":4680828,"id":"Q4680828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$E4FFF8A0-C36C-4D8C-B7EB-196E781CE96A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8e36ae8abb4652d1f90b9ad0d6e9311411c0044","datavalue":{"value":{"entity-type":"item","numeric-id":1292405,"id":"Q1292405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$6EED2A34-69F1-45C4-9E80-EE7F56AE7A43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2019b20929056393f308211e1b7badbd45ded52c","datavalue":{"value":{"entity-type":"item","numeric-id":3286636,"id":"Q3286636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$A9F37C84-8CAE-4E38-9B9E-E8B63E2E5962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"538bed55f5e1ff059e4047ada295302ed044a6c8","datavalue":{"value":{"entity-type":"item","numeric-id":5302191,"id":"Q5302191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$42486AAB-0E6F-4109-856A-2417506CC4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4203be64018c59961cbb6c7d765cd053aa8e75e3","datavalue":{"value":{"entity-type":"item","numeric-id":1327590,"id":"Q1327590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$4E7054B0-C8EA-4D80-9A0D-D1101F9CB715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$CAFA6B09-BFD7-4154-9B32-2F50DE1C1A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ee3a287812750ab8dbe538f1e4bb028b52fa851","datavalue":{"value":{"entity-type":"item","numeric-id":4000499,"id":"Q4000499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$EA144B74-4179-4849-8525-6201A0FC8580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a2c9da2fb4b6aca18f6d1fb86779342d58fb48b","datavalue":{"value":{"entity-type":"item","numeric-id":3581268,"id":"Q3581268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$25F0338A-BB80-4355-BD37-6345DDE90897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9466f370ab0906dcfe89c741d20a915cf9a349dc","datavalue":{"value":{"entity-type":"item","numeric-id":4131340,"id":"Q4131340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$030B3FB5-8A19-43EE-8508-1C943FB446B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0686d198321cac0bd952302e77346c6c9e4e8d8b","datavalue":{"value":{"entity-type":"item","numeric-id":4337982,"id":"Q4337982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$D35E4065-EA0B-4274-8FB6-8798BABA3B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66e8a62cd46463c62f9ff883109d60c4695ebc92","datavalue":{"value":{"entity-type":"item","numeric-id":4485693,"id":"Q4485693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$712F403B-D89E-4BF9-AEE0-AF79D3C9FD07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60193c791f928fe7b522c990aec98f443608e6bf","datavalue":{"value":{"entity-type":"item","numeric-id":4888348,"id":"Q4888348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q942023$051B438F-722F-4A7F-AB69-5EFF6E1B3948","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6025ef0de4d5b1b712da6b9d6402e0267ff6bbc","datavalue":{"value":"10.1007/S11512-007-0045-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q942023$BE688153-07A7-47DE-B13B-2F6BFB703F62","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d200675154c69791b6ef0e1f51ef8b57a00ab527","datavalue":{"value":{"entity-type":"item","numeric-id":2917347,"id":"Q2917347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd4d77c8ccacabe32d380a651c5d35b26114de85","datavalue":{"value":{"amount":"+0.8537409901618958","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":"Q942023$1B4F989D-DC96-4302-9032-91EA702F6832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f5ef1223ad1fcd393204c620d688269d96d249d","datavalue":{"value":{"entity-type":"item","numeric-id":5150981,"id":"Q5150981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dec1d1a035293d2eb9ba7cafb57c3da4bcc83871","datavalue":{"value":{"amount":"+0.8369368314743042","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":"Q942023$8429DD30-03D9-49E4-B5AC-57B8C4D9F98E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba02189295ea7247d7e80417a0e3d067c5dcb502","datavalue":{"value":{"entity-type":"item","numeric-id":406298,"id":"Q406298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed0e70abd2f1f34256a1015360b0746dd86a57ee","datavalue":{"value":{"amount":"+0.8275468349456787","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":"Q942023$DF4A979E-1541-45A0-81BF-96789E8DEB9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bcf46b0ac11489f62cbaefe5e5e50c12fd04686","datavalue":{"value":{"entity-type":"item","numeric-id":5024570,"id":"Q5024570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ee90ea2d53d3c89e25746b1429dce4fd9925240","datavalue":{"value":{"amount":"+0.7771225571632385","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":"Q942023$60E6B996-E3F4-4763-B8C5-42C819D1A69B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78a02f3d9ba2b74b2bfcf391ee555245afb34c94","datavalue":{"value":{"entity-type":"item","numeric-id":1292405,"id":"Q1292405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca6b6e0f85082f67ce1e7f588c3ef6a4fca8063f","datavalue":{"value":{"amount":"+0.7630425095558167","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":"Q942023$EE436F79-DF1D-4663-BBF3-70269105A31D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the computational complexity of the Riemann mapping","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_computational_complexity_of_the_Riemann_mapping"}}}}}