There are no sparse NPw-hard sets

Felipe Cucker; Dima Grigoriev

There are no sparse NP_w-hard sets

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45) › 32_Refereed conference paper (with ISBN/ISSN) › peer-review

Overview

View graph of relations

Author(s)

Felipe Cucker
Dima Grigoriev

Related Research Unit(s)

Department of Mathematics

Detail(s)

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 2001
Subtitle of host publication	26th International Symposium, MFCS 2001, Proceedings
Editors	Ales Pultr, Petr Kolman, Jiri Sgall
Publisher	Springer Verlag
Pages	285-291
Volume	2136
ISBN (Print)	9783540446835
Publication status	Published - 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2136
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Title	26th International Symposium on Mathematical Foundations of Computer Science, MFCS 2001
Place	Czech Republic
City	Marianske Lazne
Period	27 - 31 August 2001

Link(s)

	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-84974660131&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(12cf1b99-10a3-4d07-be3b-f75e8a61fe32).html

Abstract

In this paper we prove that, in the context of weak machines over IR, there are no sparse NP-hard sets.

Fingerprint

Publication fingerprints text

100

NP-complete problem Mathematics

Full Fingerprint ›

Citation Format(s)

[ RIS ] [ BibTeX ]

There are no sparse NP_w-hard sets. / Cucker, Felipe; Grigoriev, Dima.

Mathematical Foundations of Computer Science 2001: 26th International Symposium, MFCS 2001, Proceedings. ed. / Ales Pultr; Petr Kolman; Jiri Sgall. Vol. 2136 Springer Verlag, 2001. p. 285-291 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2136).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45) › 32_Refereed conference paper (with ISBN/ISSN) › peer-review

Cucker, F & Grigoriev, D 2001, There are no sparse NP_w-hard sets. in A Pultr, P Kolman & J Sgall (eds), Mathematical Foundations of Computer Science 2001: 26th International Symposium, MFCS 2001, Proceedings. vol. 2136, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2136, Springer Verlag, pp. 285-291, 26th International Symposium on Mathematical Foundations of Computer Science, MFCS 2001, Marianske Lazne, Czech Republic, 27/08/01.

Cucker, F., & Grigoriev, D. (2001). There are no sparse NP_w-hard sets. In A. Pultr, P. Kolman, & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2001: 26th International Symposium, MFCS 2001, Proceedings (Vol. 2136, pp. 285-291). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2136). Springer Verlag.

Cucker F, Grigoriev D. There are no sparse NP_w-hard sets. In Pultr A, Kolman P, Sgall J, editors, Mathematical Foundations of Computer Science 2001: 26th International Symposium, MFCS 2001, Proceedings. Vol. 2136. Springer Verlag. 2001. p. 285-291. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Cucker, Felipe ; Grigoriev, Dima. / There are no sparse NP_w-hard sets. Mathematical Foundations of Computer Science 2001: 26th International Symposium, MFCS 2001, Proceedings. editor / Ales Pultr ; Petr Kolman ; Jiri Sgall. Vol. 2136 Springer Verlag, 2001. pp. 285-291 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).