Comparisons between linear functions can help

Research output: Contribution to journalArticle

Abstract

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 [14] and Yap [16]. Several extensions are presented.

Original languageEnglish (US)
Pages (from-to)321-330
Number of pages10
JournalTheoretical Computer Science
Volume19
Issue number3
DOIs
StatePublished - Jan 1 1982
Externally publishedYes

Fingerprint

Sorting
Linear Function
Disprove
Decision problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Comparisons between linear functions can help. / Snir, Marc.

In: Theoretical Computer Science, Vol. 19, No. 3, 01.01.1982, p. 321-330.

Research output: Contribution to journalArticle

@article{1124fdd4a53a4048a529c99a79f57a56,
title = "Comparisons between linear functions can help",
abstract = "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 [14] and Yap [16]. Several extensions are presented.",
author = "Marc Snir",
year = "1982",
month = "1",
day = "1",
doi = "10.1016/0304-3975(82)90041-X",
language = "English (US)",
volume = "19",
pages = "321--330",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "3",

}

TY - JOUR

T1 - Comparisons between linear functions can help

AU - Snir, Marc

PY - 1982/1/1

Y1 - 1982/1/1

N2 - 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 [14] and Yap [16]. Several extensions are presented.

AB - 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 [14] and Yap [16]. Several extensions are presented.

UR - http://www.scopus.com/inward/record.url?scp=0347278992&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347278992&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(82)90041-X

DO - 10.1016/0304-3975(82)90041-X

M3 - Article

VL - 19

SP - 321

EP - 330

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -