[sci.math.symbolic] P = NP subclasses

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.
	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)