An example is provided of a sorting-type decision problem which can be solved in fewer steps by using comparisons between linear functions of the inputs, rather than comparisons between the inputs themselves. This disproves a conjecture of Yao  and Yap . Several extensions are presented.
|Original language||English (US)|
|Number of pages||10|
|Journal||Theoretical Computer Science|
|State||Published - Sep 1982|
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)