The shrinking property for NP and coNP

DOI10.1016/j.tcs.2010.11.035zbMath1223.68040OpenAlexW2053175898MaRDI QIDQ627189

Christian Reitwießner, Christian Glaßer, Victor L. Selivanov

Publication date: 21 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.035

zbMATH Keywords

polynomial hierarchymultivalued functionsseparation propertyshrinking propertyNPcoNPNP-pairsP-separability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Fields of algebraic numbers computable in polynomial time. II ⋮ On the main scientific achievements of Victor Selivanov ⋮ Complexity classes of equivalence problems revisited ⋮ Searching for applicable versions of computable structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fine hierarchy of regular \(\omega\)-languages
• Descriptive set theory
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• A hierarchy based on output multiplicity
• A taxonomy of complexity classes of functions
• Topology and descriptive set theory
• Optimal proof systems imply complete sets for promise classes
• Inverting onto functions.
• Separability and one-way functions
• A complexity theory for feasible closure properties
• Reductions between disjoint NP-pairs
• Degrees of models
• Inverting Onto Functions and Polynomial Hierarchy
• FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES
• The complexity of promise problems with applications to public-key cryptography
• Quantitative Relativizations of Complexity Classes
• Complexity Measures for Public-Key Cryptosystems
• Cryptocomplexity and NP-completeness
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• New Collapse Consequences of NP Having Small Circuits
• New collapse consequences of NP having small circuits
• Disjoint NP-Pairs
• Fine hierarchies and Boolean terms
• NONDETERMINISTICALLY SELECTIVE SETS
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• Fine Hierarchy of Regular Aperiodic ω-Languages

This page was built for publication: The shrinking property for NP and coNP