The Shrinking Property for NP and coNP
From MaRDI portal
Publication:3507436
DOI10.1007/978-3-540-69407-6_25zbMath1143.68017OpenAlexW2185104844MaRDI QIDQ3507436
Christian Glaßer, Christian Reitwießner, Victor L. Selivanov
Publication date: 19 June 2008
Published in: Logic and Theory of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-69407-6_25
Related Items (2)
On the main scientific achievements of Victor Selivanov ⋮ Fine hierarchies and m-reducibilities in theoretical computer science
Cites Work
- 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
- A complexity theory for feasible closure properties
- Reductions between disjoint NP-pairs
- Degrees of models
- Equivalence Relations, Invariants, and Normal Forms
- Inverting Onto Functions and Polynomial Hierarchy
- 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
- Disjoint NP-Pairs
- Fine hierarchies and Boolean terms
- 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
