On Malign Input Distributions for Algorithms

Kojiro KABAYASHI

On Malign Input Distributions for Algorithms

Kojiro KABAYASHI

Full Text Views

0

Share
Cite this

Summary :

By a measure we mean a function µ from {0, 1}^* (the set of all binary sequences) to real numbers such that µ(x)0 and µ({0, 1}^*). A malign measure is a measure such that if an input x in {0, 1}ⁿ (the set of all binary sequences of length n) is selected with the probability µ(x)/µ ({0, 1}ⁿ) then the worst-case computation time t^WO_A (n) and the average-case computation time t^av,µ_A(n) of an algorithm A for inputs of length n are functions of n of the same order for any algorithm A. Li and Vitányi found that measures that are known as a priori measures are malign. We prove that a priori" -ness and malignness are different in one strong sense.

Publication: IEICE TRANSACTIONS on Information Vol.E76-D No.6 pp.634-640

Publication Date: 1993/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm and Computational Complexity

Cite this

Copy

Kojiro KABAYASHI, "On Malign Input Distributions for Algorithms" in IEICE TRANSACTIONS on Information, vol. E76-D, no. 6, pp. 634-640, June 1993, doi: .
Abstract: By a measure we mean a function µ from {0, 1}^* (the set of all binary sequences) to real numbers such that µ(x)0 and µ({0, 1}^*). A malign measure is a measure such that if an input x in {0, 1}ⁿ (the set of all binary sequences of length n) is selected with the probability µ(x)/µ ({0, 1}ⁿ) then the worst-case computation time t^WO_A (n) and the average-case computation time t^av,µ_A(n) of an algorithm A for inputs of length n are functions of n of the same order for any algorithm A. Li and Vitányi found that measures that are known as a priori measures are malign. We prove that a priori" -ness and malignness are different in one strong sense.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e76-d_6_634/_p

Copy

@ARTICLE{e76-d_6_634,
author={Kojiro KABAYASHI, },
journal={IEICE TRANSACTIONS on Information},
title={On Malign Input Distributions for Algorithms},
year={1993},
volume={E76-D},
number={6},
pages={634-640},
abstract={By a measure we mean a function µ from {0, 1}^* (the set of all binary sequences) to real numbers such that µ(x)0 and µ({0, 1}^*). A malign measure is a measure such that if an input x in {0, 1}ⁿ (the set of all binary sequences of length n) is selected with the probability µ(x)/µ ({0, 1}ⁿ) then the worst-case computation time t^WO_A (n) and the average-case computation time t^av,µ_A(n) of an algorithm A for inputs of length n are functions of n of the same order for any algorithm A. Li and Vitányi found that measures that are known as a priori measures are malign. We prove that a priori" -ness and malignness are different in one strong sense.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - On Malign Input Distributions for Algorithms
T2 - IEICE TRANSACTIONS on Information
SP - 634
EP - 640
AU - Kojiro KABAYASHI
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E76-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1993
AB - By a measure we mean a function µ from {0, 1}^* (the set of all binary sequences) to real numbers such that µ(x)0 and µ({0, 1}^*). A malign measure is a measure such that if an input x in {0, 1}ⁿ (the set of all binary sequences of length n) is selected with the probability µ(x)/µ ({0, 1}ⁿ) then the worst-case computation time t^WO_A (n) and the average-case computation time t^av,µ_A(n) of an algorithm A for inputs of length n are functions of n of the same order for any algorithm A. Li and Vitányi found that measures that are known as a priori measures are malign. We prove that a priori" -ness and malignness are different in one strong sense.
ER -