Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!hubcap!steve
From: steve@hubcap.UUCP ("Steve" Stevenson)
Newsgroups: comp.ai,sci.math.symbolic
Subject: Re: P = NP subclasses
Message-ID: <455@hubcap.UUCP>
Date: Tue, 15-Sep-87 08:11:07 EDT
Article-I.D.: hubcap.455
Posted: Tue Sep 15 08:11:07 1987
Date-Received: Thu, 17-Sep-87 02:09:35 EDT
References: <1035@aurora.UUCP>
Organization: Clemson University, Clemson, SC
Lines: 13
Summary: Looking for subclass to P=NP
Xref: mnetor comp.ai:771 sci.math.symbolic:153

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