A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions

Glasser, Christian; Hemaspaandra, Lane A.

A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions

Authors

Description

This paper discusses advances, due to the work of Cai, Naik, and Sivakumar and Glasser, in the complexity class collapses that follow if NP has sparse hard sets under reductions weaker than (full) truth-table reductions.
20 pages, 1 table

Keywords

Computational Complexity, Data Structures and Algorithms, F.1.3; F.1.2

URI

http://salesiana.dossiersoluciones.com/handle/123456789/30458

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0011019
http://arxiv.org/abs/cs/0011019

Collections

arXiv

Full item page

A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Keywords

Citation

URI

Consulte el texto completo en el siguiente enlace:

Collections