The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] input distributions(1hit)

1-1hit
  • On Malign Input Distributions for Algorithms

    Kojiro KABAYASHI  

     
    PAPER-Algorithm and Computational Complexity

      Vol:
    E76-D No:6
      Page(s):
    634-640

    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}n (the set of all binary sequences of length n) is selected with the probability µ(x)/µ ({0, 1}n) then the worst-case computation time tWOA (n) and the average-case computation time tav,µ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.