scientific article; zbMATH DE number 3845567
[For the entire collection see Zbl 0511.00030.] This paper considers sets of different densities in NP, especially sparse ones, i.e., sets that have only polynomially many elements of length n. It is shown that there exists a set that is complete for sparse sets in NP under Turing reductions. It is also shown that sets in NP of low density are easy to recognize if and only if higher complexity classes, like EXPTIME, NEXPTIME, etc. completely or partially collapse. The proofs are based on the idea to consider for sets of high complexity the corresponding sets of unary representations of their elements, which is a sparse set in NP. Finally the results are connected to the difficulty of proofs or representations of proofs in axiomatized mathematical systems.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3315500)