{"entities":{"Q750150":{"pageid":751999,"ns":120,"title":"Item:Q750150","lastrevid":64093008,"modified":"2026-04-11T17:35:16Z","type":"item","id":"Q750150","labels":{"en":{"language":"en","value":"On the complexity of topological sorting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4174325"}},"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":"Q750150$CCBCF7E4-2C16-4DB5-982E-7C6F4B77E549","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2658ef122b4e25abd8e5d606f2cec6ca53f8910c","datavalue":{"value":{"text":"On the complexity of topological sorting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q750150$3F0ACA0F-889D-41D9-8171-7E67FD7C4FA0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"91e7bdf839d5c6956df08f3fa7467e142448890a","datavalue":{"value":"0713.68025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750150$059CA02F-5D67-4E44-B3A3-247D97134BCE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9d64bdbd9aa8e270b6ba638b93c028a6a7eecb0e","datavalue":{"value":"10.1016/0020-0190(90)90050-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750150$16D659F5-B1AB-4619-B938-0953B383FC0F","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":"Q750150$5CFD7E23-F3BB-4850-8263-E9E5BDFAB23E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q750150$D8866516-4C5B-4BC1-8B4E-CFB160AF1317","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b2c9174926dfa4b78c43dcdbd9befa667d7eb74a","datavalue":{"value":"If a digraph is acyclic (has no directed cycles), a polynomial sequential algorithm can perform a topological sort on its vertices - that is, label them 1,2,...,n so that arcs go only from vertices with smaller labels to vertices with larger labels. The parallel complexity of this problem has been successively reduced from \\(NC^ 2\\) to \\(NL^*\\) to \\(FL^{NL}\\) [see \\textit{S. A. Cook}, Inf. Control 64, 2-22 (1985; Zbl 0575.68045) for definitions of parallel complexity classes]. In Cook [loc. cit.] the problem was posed as to whether this problem is NL (non-deterministic log-space)-hard under \\(NC^ 1\\)-reducibility and answered in the affirmative if the algorithm is required to state whether the digraph is acyclic (since deciding whether a digraph is acyclic is NL-hard) but left open otherwise. The author shows that topological sorting is NL-hard even if the algorithm is required merely to topologically sort a digraph which happens to be acyclic and is allowed to label its vertices arbitrarily otherwise.    In case the graph has no cycles, directed or undirected, the article presents a DL (deterministic log-space) topological sorting algorithm. It was shown in \\textit{S. A. Cook} and \\textit{P. McKenzie} [J. Algorithms 8, 385-394 (1987; Zbl 0644.68058)] that deciding whether an undirected graph is acyclic is DL-complete; the article under review proves that topological sorting is DL-complete even if the algorithm is not required to state whether the underlying undirected graph is acyclic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q750150$27CA2E71-BB31-4EA6-B5F1-18D20E057920","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750150$1FC3980F-797C-4EC9-950B-3AE8A4ED063A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750150$CE6BC770-FC37-4A33-A914-2CB6EF31415D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750150$04403AE3-E1EF-4043-A581-F06EB7B18F87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750150$A7B5D76E-A34F-48C6-81B7-BA6C5ED95F93","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71282ba86abe578e8f8ca16b82180002148a5c26","datavalue":{"value":"4174325","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750150$3710A637-465E-4AD3-8941-DA68097C4840","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f807575e93d1d3c1eabfae65ba1e234902efc3a","datavalue":{"value":"topological sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q750150$7E061F5F-B4AD-4B95-AD46-B2C526CE4EE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"298a551ef47c5b20057a4bfdb8bbc9e28d84ca03","datavalue":{"value":"acyclic digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q750150$38943FC8-92E4-4CD0-9AFF-B28488443FE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q750150$16391D4B-8BBD-4673-8B24-C2BB19DEB631","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q750150$3B7D2446-BD54-4DE8-A080-D349CBAB1986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9864c2fab8ff6f6a7cbed64d92db42aebc3ab755","datavalue":{"value":"NL-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q750150$C670FBA7-2159-4502-8E7F-7B53367A682D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750150$8DBE5387-AC66-4D95-BFCF-9405DBA4AB32","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":"Q750150$E12E148E-E5AA-4CED-9067-12EA5A9B21C9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4883716dcf629a9b14cb1382ee8b90d179c40116","datavalue":{"value":"https://doi.org/10.1016/0020-0190(90)90050-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q750150$2D1B68B1-68EB-40CE-9F78-8C2A2FAC9A98","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"42b390ba780c31f626e49ff2d4f4bcfdb5d572ad","datavalue":{"value":"W2043398952","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750150$667554B4-1949-4269-9DF4-0FA69372D19D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750150$588DAC2C-DBE3-4E8E-BF9C-D8870EB1BBC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b23a99da8df474d603cdef7b4c76229f6a312c3","datavalue":{"value":{"entity-type":"item","numeric-id":3787477,"id":"Q3787477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750150$D7E40CC1-9E8A-4CD8-8F6A-44F3FD88B03E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f6f2fa62f920fb46fbd79ba851e5cbf1f877777","datavalue":{"value":{"entity-type":"item","numeric-id":3922163,"id":"Q3922163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750150$B0E97408-0097-4809-ADFA-39B28180FA7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750150$0710DB0A-6D09-4565-8DC0-FAF9FEDEFD56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bcd71ac0ee1662e3c5c0f5046af9d7c75419ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1221749,"id":"Q1221749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750150$BC7952C6-30B9-45BD-BF1A-F0EDA1F3B59B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67ed33de7061de4d7d8391bea59c71fda756b59c","datavalue":{"value":{"entity-type":"item","numeric-id":3815544,"id":"Q3815544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750150$78661E78-6C78-492E-820F-BBCBB1549CF1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e832b00754043ec682c7c28be4295321f126a9a7","datavalue":{"value":{"entity-type":"item","numeric-id":5406271,"id":"Q5406271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b090eab346f08d85f7da68b323dee7552b5c53c1","datavalue":{"value":{"amount":"+0.76066065","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$DD73417B-DB96-4A08-B1B2-DB31BADCC5F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d683f6e81c40096ab645eb032326dcd327806abd","datavalue":{"value":{"entity-type":"item","numeric-id":3727396,"id":"Q3727396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"667a09b7d87c4601bee2a49c1e640055fa39ad9f","datavalue":{"value":{"amount":"+0.7596773","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$3B3AFC5A-F70D-470A-98AF-3A1691EA2F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65462dbd980649486e94c98754935ffbf9ba7b2c","datavalue":{"value":{"entity-type":"item","numeric-id":3415000,"id":"Q3415000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea9907fa98d0c2c2d3a3d8bac2edea1a4344f79b","datavalue":{"value":{"amount":"+0.7592653","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$792EEEA4-D243-4B1C-B5D7-C3841440CDE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c94d9eeb8c34326c05f41826d6aefa515fdd9d39","datavalue":{"value":{"entity-type":"item","numeric-id":6058233,"id":"Q6058233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69d8e57316ce279cef7b9e3ae2a760df5355867b","datavalue":{"value":{"amount":"+0.750218","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$E0711A24-1C19-408C-8B4E-559720E83CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e154cac198979b48a5323bfa3b4b6955578111cb","datavalue":{"value":{"entity-type":"item","numeric-id":1402302,"id":"Q1402302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f99c2c10e1a2e9af815e5353b3cb423b4faf59e3","datavalue":{"value":{"amount":"+0.74935865","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$52D6E0D2-36C3-4779-8157-91678388432A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c063c6009b014ae7256d39341d870f81e792f59f","datavalue":{"value":{"entity-type":"item","numeric-id":3787477,"id":"Q3787477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24a5a26fd680c6c37a2e767d65a5e9d983a810ac","datavalue":{"value":{"amount":"+0.7488244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$B45CEBA2-290C-4C19-9AF5-6BF0F9CC78D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ec980743caf97e59983ffabd2f9c82a36dd4111","datavalue":{"value":{"entity-type":"item","numeric-id":5236310,"id":"Q5236310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41a6766fea2fe070bbfbbfc9e77d64925b18cb40","datavalue":{"value":{"amount":"+0.74545616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$707421AA-178B-479C-AE0E-C20DF8AC528C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8e55e695f6a9c3a16b61189e2fe93bf34023337","datavalue":{"value":{"entity-type":"item","numeric-id":5233709,"id":"Q5233709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cafa774d585cbf5544538f44e7dcdbcdfa599f4d","datavalue":{"value":{"amount":"+0.7433261","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$54F4A135-F980-4F6B-8EF0-BE870AFDCBE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa548257d126809769123e11e84b984428318378","datavalue":{"value":{"entity-type":"item","numeric-id":582104,"id":"Q582104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8afd5daaa5de7f1335cb405a1fa7bb3bdda5e70e","datavalue":{"value":{"amount":"+0.74152684","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$C9DD59C1-DCB5-4C5E-9336-E10DE09D727C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d84ecb4bda0e4c6e3b2a2647f5f6b823a99df910","datavalue":{"value":{"entity-type":"item","numeric-id":1062456,"id":"Q1062456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7411f390083cccfd3c24497030bcac0e3f9794c","datavalue":{"value":{"amount":"+0.73958725","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q750150$B878EB8B-1E75-42B0-8BD9-269852A87A11","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b46006266dfa27f78f67dac26590ca028f0108a7","datavalue":{"value":{"entity-type":"item","numeric-id":6482543,"id":"Q6482543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750150$17974F21-3B13-4014-B91C-3B9D3D90FC47","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of topological sorting","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_topological_sorting"}}}}}