**steve@hubcap.UUCP ("Steve" Stevenson)** (09/15/87)

I once heard a commment that most instances of "NP-complete" problems encountered in practice do not exhibit the pathological behavior of the exponential growth function. Take your favorite characterization of the NP-complete problem. Questions: What is the largest subclass of instances (decidable or not) which does not exhibit the exponetial? What is the largest Turing-decidable subclass? -- Steve (really "D. E.") Stevenson steve@hubcap.clemson.edu Department of Computer Science, (803)656-5880.mabell Clemson University, Clemson, SC 29634-1906

**bergman@rocky2.UUCP (Mark Bergman)** (10/16/87)

ihasdjhadajdkasjdkasj