Average case completeness

This publication has 10 references indexed in Scilit:

• On the reduction theory for average case complexity
  Published by Springer Nature ,1991
• Expected Computation Time for Hamiltonian Path problem
  SIAM Journal on Computing, 1987
• The decision problem for the probabilities of higher-order properties
  Published by Association for Computing Machinery (ACM) ,1987
• Average polynomial time complexity of some NP-complete problems
  Theoretical Computer Science, 1986
• Average Case Complete Problems
  SIAM Journal on Computing, 1986
• Some Examples of Combinatorial Averaging
  The American Mathematical Monthly, 1985
• The NP-completeness column: An ongoing guide
  Journal of Algorithms, 1984
• On the definitions of some complexity classes of real numbers
  Theory of Computing Systems, 1983
• Complexity results for classes of quantificational formulas
  Journal of Computer and System Sciences, 1980
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
  Russian Mathematical Surveys, 1970