ON THE STRUCTURE OF NPC

Authors
MALAJOVICH G MEER K
Citation
G. Malajovich et K. Meer, ON THE STRUCTURE OF NPC, SIAM journal on computing (Print), 28(1), 1999, pp. 27-35
Citations number
12
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
28
Issue
1
Year of publication
1999
Pages
27 - 35
Database
ISI
SICI code
0097-5397(1999)28:1<27:>2.0.ZU;2-6
Abstract
This paper deals with complexity classes P-C and NPC as they were intr oduced over the complex numbers by Blum, Shub, and Smale [Bull. Amer. Math. Soc., 21 (1989), p. 1]. Under the assumption P-C not equal NPC t he existence of noncomplete problems in NPC not belonging to P-C is es tablished.