{"entities":{"Q1183942":{"pageid":1194691,"ns":120,"title":"Item:Q1183942","lastrevid":47058427,"modified":"2025-12-31T13:17:29Z","type":"item","id":"Q1183942","labels":{"en":{"language":"en","value":"Counting linear extensions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33906"}},"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":"Q1183942$7AEB580F-B68E-4BE0-BDE2-246A50C4B2BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"21012186337b0f33d0fdc5d1f2f9226e12bf7b18","datavalue":{"value":{"text":"Counting linear extensions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183942$2E6401E4-2D7D-4EFC-8871-DD2D18069F7A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f24b5ea3159b13b6f82588a9602b384f05ff2b6e","datavalue":{"value":"0759.06001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183942$4B8D82B4-5B5C-4B07-971C-4446372F6FBC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"61aa597604abb0f8fa15ec2e020a78867e02ba66","datavalue":{"value":"10.1007/BF00383444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183942$6441E42E-F810-4408-A3A5-E69C3C1213A7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$09CA521C-EA0A-4753-9685-C80A21CBB560","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183942$F697999C-C7B3-46E3-875A-594746744200","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fcbf4dc04478d760702cca2dd9ca3107fb929eda","datavalue":{"value":"The problem of counting all linear extensions of a poset \\(P\\) (whose number is denoted by \\(N(P)\\)) is known to be very difficult, and in computer science it is important, e.g. in sorting algorithms. Although there exist polynomial algorithms for computing \\(N(P)\\) for certain special classes of posets, and even randomized polynomial-time algorithms, for the entire class of posets, for estimating \\(N(P)\\) with an arbitrary given approximation, it has been conjectured that this counting problem is \\(\\# P\\)-complete (in the sense of L. G. Valiant). The authors solve the conjecture affirmatively, in fact only for posets of height at most 5 (the construction may be modified so as to get the height down to 3, but it seems that for posets of height 2, a different one is needed). The proof consists in a ``reduction'' of the given problem to the 3-SAT Count Problem, showing that, with the help of an oracle which counts linear extensions, a Turing machine can count the number of satisfying assignments to an instance of 3-SAT in polynomial time. The paper is also a valuable survey of the existing randomized algorithms for estimating \\(N(P)\\) and it discusses some consequences of the proven result on other related problems (e.g. the problem of computing the volume of a rational polyhedron). Much of this work has previously been published as an extended abstract [``Counting linear extensions is \\(\\# P\\)-complete'', Proc. 23 rd ACM Symp. Theory of Computing, 175-181 (1991)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183942$43DD0008-4838-4045-B150-EE384CFFCEE5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183942$235407A7-BEFB-46FF-908E-C2D5FD95AEE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183942$54FA7272-4349-408D-BC9B-BDA4B37A8359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183942$AF3AD220-5F70-4C84-851A-6C73112DC7D2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d60fafaba30243e73e9f28a60fcb7f8ccc69a656","datavalue":{"value":"33906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183942$0E322829-C782-4767-B359-DB96D394AF88","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27e2fd92223161d9ea2645b8076cee77c9dfcb90","datavalue":{"value":"number of linear extensions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183942$1084F274-2B2C-4BA0-AF11-13F50CF60AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bf072d8ef007a91c55d38cfb7894831477ca36d","datavalue":{"value":"\\(\\# P\\)-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183942$1EEBFA29-4C63-40D0-A05A-0A3D8BCFAD1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f80defb0c6d49ac2be62b0064c67a85d5b3a683","datavalue":{"value":"3-SAT Count Problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183942$D7882231-EAE5-4C4B-8663-B4EBB46CDF75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49eb4dac5aeb1a5fd4804122c81f369b6968def6","datavalue":{"value":"randomized algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183942$BB4EBCB4-7273-48C2-BFC5-AE151192E253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b66c34ba391c4b8a3e6b81d3eabb51b04dda292","datavalue":{"value":"volume of a rational polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183942$CE5B190F-0203-4B0D-8AA7-80B488C55B62","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bfcb09213070024009ff0e178214cb32bc73bdec","datavalue":{"value":"Q55885264","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183942$601AB61C-36D4-4AC1-8303-B2C5A2A9FD2A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa1c283669072b9efd9a8b4d0e623734e03b4535","datavalue":{"value":{"entity-type":"item","numeric-id":918998,"id":"Q918998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$E38DC143-ADEE-4EFB-A3BF-DD5B6A0DEE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ed046cfa0f3aaebe7ee5a321838d2b14a94a270","datavalue":{"value":{"entity-type":"item","numeric-id":221782,"id":"Q221782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$FD53E25A-B66A-4F9C-A609-3734A1CB7477","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6536f759dee9ce142c834adc5cc137400d919eb8","datavalue":{"value":{"entity-type":"item","numeric-id":1037240,"id":"Q1037240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$86C7E273-4A4A-4F5A-B1BA-6B2E1E163E48","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":"Q1183942$74CDC5B9-3562-44C5-A7D6-94072B694419","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"577e14802337b24d59b7ffc85ad258c51defcd6e","datavalue":{"value":{"entity-type":"item","numeric-id":3760585,"id":"Q3760585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$A5E510D0-BC77-4EFB-AC3E-1DC1049876BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7245281c6be433cd059d40b2ec4640fe00cf4da","datavalue":{"value":{"entity-type":"item","numeric-id":1108016,"id":"Q1108016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$71E81823-F5C7-4168-84D8-DFC09203A742","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3c0e607f49337c746be7e698564085866acdb20","datavalue":{"value":{"entity-type":"item","numeric-id":1183942,"id":"Q1183942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$B55D1BCD-35BC-4455-A6FF-769E6EF89085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98ff388f1854cc1183de8af7335052d365ad39ee","datavalue":{"value":{"entity-type":"item","numeric-id":3821581,"id":"Q3821581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$1EC07064-96B6-41BB-BA02-1C06D40D3754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf5b138671d18dd2cdcde19ee38428fcef4d1e28","datavalue":{"value":{"entity-type":"item","numeric-id":3976408,"id":"Q3976408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$F8AF5CC4-292A-4F4E-83DD-B8964DE690D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003cec5e45239de461023a385e31f5931da25ca0","datavalue":{"value":{"entity-type":"item","numeric-id":4088327,"id":"Q4088327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$81362E5E-3DCF-42AC-A715-2931CE7600B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cb473c6026106fce5ad49a54be284a927657c08","datavalue":{"value":{"entity-type":"item","numeric-id":1086264,"id":"Q1086264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$B423E916-A1D8-4CE8-B9E7-9EE5D2925DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1f6aa5a7dbb8eced91175201c5b61a84466f7ef","datavalue":{"value":{"entity-type":"item","numeric-id":3259107,"id":"Q3259107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$98F3E00D-79D7-4451-BF0E-CE8A30154B1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2f9f6d0530a37c14341792cf99213450cd4d01a","datavalue":{"value":{"entity-type":"item","numeric-id":2266032,"id":"Q2266032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$1BFB2E0D-A859-4DF1-810A-BD1A6D2096DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc0dd122034ac145f37652ad6c5626356242996e","datavalue":{"value":{"entity-type":"item","numeric-id":1182035,"id":"Q1182035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$B8A5E21B-DB4D-4476-945A-00A956233601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f92191d0b56ccd98870719b6e256abcd47d47f0b","datavalue":{"value":{"entity-type":"item","numeric-id":3138745,"id":"Q3138745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$6EAC9675-224B-455C-97E4-44D6A13195C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"677b40da98450bce11a8d5e79ffcef1cbe3eef48","datavalue":{"value":{"entity-type":"item","numeric-id":909681,"id":"Q909681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$2225A75C-5BC9-4F6B-982D-E6EA7A81A1D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c07fb145c190b934a8c9134d7ebb9e5f3699a07e","datavalue":{"value":{"entity-type":"item","numeric-id":3730017,"id":"Q3730017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$6EC85573-8454-4AB4-B373-1C6CA3BFCEA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0139576536049f192dbdc00c70bbdb66e6021f1","datavalue":{"value":{"entity-type":"item","numeric-id":805042,"id":"Q805042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$2D3188FC-F859-42D9-A863-FB958D6B28FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3798f797f1d96df74883f771f001f3f714b860f0","datavalue":{"value":{"entity-type":"item","numeric-id":3036719,"id":"Q3036719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$4434BDB8-B767-40A2-926F-C9E0513D93A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d79a0774bbccf1180e30253d0f82980850393519","datavalue":{"value":{"entity-type":"item","numeric-id":1117955,"id":"Q1117955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$982CAA5F-290A-4220-A937-1FA1057E63C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48dee668c94abc020e96907639b1e599d7ed0a36","datavalue":{"value":{"entity-type":"item","numeric-id":5284063,"id":"Q5284063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$C4EB64DA-D56A-40E5-BCA6-2406DC806864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$80216DBA-CBB8-4586-BFCE-FAEF0070269F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70536879af054717c0f3d9d913a10e93c328980d","datavalue":{"value":{"entity-type":"item","numeric-id":3853129,"id":"Q3853129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$4010D474-A198-4CF4-9281-7FFD14E7F432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1b78d9fd365d1c88881f97c3a5a5d73d889cc86","datavalue":{"value":{"entity-type":"item","numeric-id":1163038,"id":"Q1163038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183942$ADF9BEFE-47BF-4AC6-83CD-23C1387BD88B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d6bbbe4ce8dce33c89fbcdc5b5379b36641b139","datavalue":{"value":{"entity-type":"item","numeric-id":2215472,"id":"Q2215472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec2907e448ae28198e641d9821584525b1712f04","datavalue":{"value":{"amount":"+0.8716898560523987","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":"Q1183942$63E31036-5773-47FB-B8EE-41D9BEAEBB8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1893203e9469836c82a2262536caba34fa9026f","datavalue":{"value":{"entity-type":"item","numeric-id":4291563,"id":"Q4291563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2db204589470720c46d86b739674e829cc761cc1","datavalue":{"value":{"amount":"+0.8527530431747437","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":"Q1183942$35C24B34-E37E-40FC-9C1F-92965ED29C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efe3132b2f9f3dbbd67b8948642f1dea42a3ad8a","datavalue":{"value":{"entity-type":"item","numeric-id":1917670,"id":"Q1917670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"793609e2e7469898908dcdb35525cf99e7e4eb50","datavalue":{"value":{"amount":"+0.8504992127418518","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":"Q1183942$10A97410-8EEC-443A-8BB2-C88EE74B4846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59c5c91a4254fb9495e8d031a68a106d03fb5a56","datavalue":{"value":{"entity-type":"item","numeric-id":6039921,"id":"Q6039921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93cab7ce0bd4b7b7803dbbec2cfadf8d0c91ada5","datavalue":{"value":{"amount":"+0.8498504161834717","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":"Q1183942$F34669AB-DB13-4322-B353-23793629C708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca538f115db43a5473cd8298d45fa4fe2fe30576","datavalue":{"value":{"entity-type":"item","numeric-id":1739113,"id":"Q1739113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa5e9fbad9598c94904e401f0de86dbb60a86f73","datavalue":{"value":{"amount":"+0.8493797779083252","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":"Q1183942$1719282B-0F8F-4703-9BAB-E3A0A5420CF6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1183942","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1183942"}}}}}