Use this resource - and many more! - in your textbook!
AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.
The power of witness reduction
By: Gupta, S.;
1991 / IEEE / 0-8186-2255-5
This item was taken from the IEEE Periodical ' The power of witness reduction ' Recent results by M. Ogiwara and L.A. Hemachandra (1990) established a connection between functions being hard for a class of functions and functions interacting with the class to effect witness reduction. The author believes that the ability to achieve some form of witness reduction is what makes a function hard for a class of functions. To support this thesis he defines new function classes and obtains results analogous to those of Ogiwara and Hemachandra. He also introduces the notion of randomly hard functions and obtains similar results.<