There are no sparse NPw-hard sets

Felipe Cucker; Dima Grigoriev

doi:10.1007/3-540-44683-4_25

There are no sparse NP_w-hard sets

Felipe Cucker
, Dima Grigoriev

Department of Mathematics

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

In this paper we prove that, in the context of weak machines over ℝ, there are no sparse NP-hard sets. © Springer-Verlag Berlin Heidelberg 2001

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 2001
Subtitle of host publication	26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001 Proceedings
Editors	Ales Pultr, Petr Kolman, Jiri Sgall
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	285-291
ISBN (Electronic)	978-3-540-44683-5
ISBN (Print)	9783540446835
DOIs	https://doi.org/10.1007/3-540-44683-4_25
Publication status	Published - 2001
Event	26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001) - Marianske Lazne, Czech Republic Duration: 27 Aug 2001 → 31 Aug 2001

Publication series

Name	Lecture Notes in Computer Science
Volume	2136
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001)
Place	Czech Republic
City	Marianske Lazne
Period	27/08/01 → 31/08/01

Access Output

10.1007/3-540-44683-4_25

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

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 Marianske Lazne, Czech Republic, August 27-31, 2001 Proceedings (pp. 285-291). (Lecture Notes in Computer Science; Vol. 2136). Springer . https://doi.org/10.1007/3-540-44683-4_25

@inproceedings{12cf1b9910a34d07be3bf75e8a61fe32,

title = "There are no sparse NPw-hard sets",

abstract = "In this paper we prove that, in the context of weak machines over ℝ, there are no sparse NP-hard sets. {\textcopyright} Springer-Verlag Berlin Heidelberg 2001",

author = "Felipe Cucker and Dima Grigoriev",

year = "2001",

doi = "10.1007/3-540-44683-4\_25",

language = "English",

isbn = "9783540446835",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "285--291",

editor = "Ales Pultr and Petr Kolman and Jiri Sgall",

booktitle = "Mathematical Foundations of Computer Science 2001",

note = "26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001) ; Conference date: 27-08-2001 Through 31-08-2001",

}

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 Marianske Lazne, Czech Republic, August 27-31, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2136, Springer , Berlin, Heidelberg, pp. 285-291, 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001), Marianske Lazne, Czech Republic, 27/08/01. https://doi.org/10.1007/3-540-44683-4_25

There are no sparse NP_w-hard sets. / Cucker, Felipe; Grigoriev, Dima.
Mathematical Foundations of Computer Science 2001: 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001 Proceedings. ed. / Ales Pultr; Petr Kolman; Jiri Sgall. Berlin, Heidelberg: Springer , 2001. p. 285-291 (Lecture Notes in Computer Science; Vol. 2136).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - There are no sparse NPw-hard sets

AU - Cucker, Felipe

AU - Grigoriev, Dima

PY - 2001

Y1 - 2001

N2 - In this paper we prove that, in the context of weak machines over ℝ, there are no sparse NP-hard sets. © Springer-Verlag Berlin Heidelberg 2001

AB - In this paper we prove that, in the context of weak machines over ℝ, there are no sparse NP-hard sets. © Springer-Verlag Berlin Heidelberg 2001

UR - https://www.scopus.com/pages/publications/84974660131

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84974660131&origin=recordpage

U2 - 10.1007/3-540-44683-4_25

DO - 10.1007/3-540-44683-4_25

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783540446835

T3 - Lecture Notes in Computer Science

SP - 285

EP - 291

BT - Mathematical Foundations of Computer Science 2001

A2 - Pultr, Ales

A2 - Kolman, Petr

A2 - Sgall, Jiri

PB - Springer

CY - Berlin, Heidelberg

T2 - 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001)

Y2 - 27 August 2001 through 31 August 2001

ER -

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 Marianske Lazne, Czech Republic, August 27-31, 2001 Proceedings. Berlin, Heidelberg: Springer . 2001. p. 285-291. (Lecture Notes in Computer Science). doi: 10.1007/3-540-44683-4_25