1/3–2/3 conjecture

1/3–2/3 conjecture

Jesse Russell Ronald Cohn

     

бумажная книга



ISBN: 978-5-5147-1546-6

High Quality Content by WIKIPEDIA articles! In order theory, a branch of mathematics, the 1/3–2/3 conjecture states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible sorted orders by a factor of 2/3 or better. Equivalently, in every finite partially ordered set that is not totally ordered, there exists a pair of elements x and y with the property that at least 1/3 and at most 2/3 of the linear extensions of the partial order place x earlier than y.