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