Open AccessThe Complexity of Malign Ensembles
Author(s) -
Peter Bro Miltersen
Publication year - 1990
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v19i335.6565
Subject(s) - time complexity , class (philosophy) , property (philosophy) , running time , exponential function , polynomial , mathematics , discrete mathematics , computer science , upper and lower bounds , combinatorics , algorithm , artificial intelligence , mathematical analysis , philosophy , epistemology
We analyze the concept of malignness , which is the property of probability ensembles of making the average case running time equal to the worst case running time for a class of algorithms. We derive lower and upper bounds on the complexity of malign ensembles, which are tight for exponential time algorithms, and which show that no polynomial time computable malign ensemble exists for the class of superlinear algorithms. Furthermore, we show that for no class of superlinear algorithms a polynomial time computable malign ensemble exists, unless every language in P has an expected polynomial time constructor.