Agrawal, M. ; Biswas, S. (1996) NP-creative sets: a new class of creative sets in NP Theory of Computing Systems, 29 (5). pp. 487-505. ISSN 1432-4350
![[img]](http://repository.ias.ac.in/style/images/fileicons/application_pdf.png)
|
PDF
- Publisher Version
199kB |
Official URL: http://www.springerlink.com/content/w51357543356m7...
Related URL: http://dx.doi.org/10.1007/BF01184812
Abstract
We obtain a new definition of creativeness for NP, called NP-creativeness. We show that all NP-creative sets are NP-complete and provide strong evidence that all known NP-complete sets are NP-creative. We also show that all NP-creative sets are complete under exponentially honest reductions and contain an infinite NP subset in their complement (in other words, they are not NP-simple).
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| ID Code: | 20253 |
| Deposited On: | 20 Nov 2010 14:47 |
| Last Modified: | 17 May 2016 04:37 |
Repository Staff Only: item control page
