On sparseness, reducibilities, and complexity

Felipe Cucker

doi:10.1016/j.apal.2004.06.011

On sparseness, reducibilities, and complexity

Felipe Cucker

Department of Mathematics

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Abstract

We prove several results about the existence of sparse sets complete (and hard) for Turing reductions on different settings and complexity classes over the real numbers. © 2004 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	53-61
Journal	Annals of Pure and Applied Logic
Volume	134
Issue number	1 SPEC. ISS.
DOIs	https://doi.org/10.1016/j.apal.2004.06.011
Publication status	Published - Jun 2005

Research Keywords

Real computation
Sparse sets
Turing reductions

Access Output

10.1016/j.apal.2004.06.011Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{913028bf858541a2bbf77f3db32b3c30,

title = "On sparseness, reducibilities, and complexity",

abstract = "We prove several results about the existence of sparse sets complete (and hard) for Turing reductions on different settings and complexity classes over the real numbers. {\textcopyright} 2004 Elsevier B.V. All rights reserved.",

keywords = "Real computation, Sparse sets, Turing reductions",

author = "Felipe Cucker",

year = "2005",

month = jun,

doi = "10.1016/j.apal.2004.06.011",

language = "English",

volume = "134",

pages = "53--61",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier B.V.",

number = "1 SPEC. ISS.",

}

TY - JOUR

T1 - On sparseness, reducibilities, and complexity

AU - Cucker, Felipe

PY - 2005/6

Y1 - 2005/6

N2 - We prove several results about the existence of sparse sets complete (and hard) for Turing reductions on different settings and complexity classes over the real numbers. © 2004 Elsevier B.V. All rights reserved.

AB - We prove several results about the existence of sparse sets complete (and hard) for Turing reductions on different settings and complexity classes over the real numbers. © 2004 Elsevier B.V. All rights reserved.

KW - Real computation

KW - Sparse sets

KW - Turing reductions

UR - http://www.scopus.com/inward/record.url?scp=17044421212&partnerID=8YFLogxK

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

U2 - 10.1016/j.apal.2004.06.011

DO - 10.1016/j.apal.2004.06.011

M3 - RGC 21 - Publication in refereed journal

SN - 0168-0072

VL - 134

SP - 53

EP - 61

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 1 SPEC. ISS.

ER -

On sparseness, reducibilities, and complexity

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this