Strong nondeterministic polynomial-time reducibilities
From MaRDI portal
Publication:1055405
DOI10.1016/0304-3975(82)90085-8zbMath0521.03028OpenAlexW2041317738MaRDI QIDQ1055405
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90085-8
Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
On reductions of NP sets to sparse sets, Collapsing degrees via strong computation, Locating \(P\)/poly optimally in the extended low hierarchy, Separating the low and high hierarchies by oracles, Decompositions of nondeterministic reductions, Graph isomorphism is in the low hierarchy, On the complexity of graph reconstruction, On closure properties of bounded two-sided error complexity classes, Characterizing polynomial complexity classes by reducibilities, Promise problems and access to unambiguous computation, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Unnamed Item, Robust machines accept easy sets, A uniform approach to obtain diagonal sets in complexity classes, Reductions on NP and p-selective sets, The consequences of eliminating NP solutions, Fault-tolerance and complexity (Extended abstract), Strong and robustly strong polynomial-time reducibilities to sparse sets, Separating complexity classes with tally oracles, Some results on selectivity and self-reducibility, The complexity of two problems on arithmetic circuits, New collapse consequences of NP having small circuits, Logarithmic advice classes, Counting classes: Thresholds, parity, mods, and fewness, On sparse hard sets for counting classes, Competing provers yield improved Karp-Lipton collapse results, The robustness of LWPP and WPP, with an application to graph reconstruction, Reducibilities on tally and sparse sets, Dot operators, Almost-everywhere complexity hierarchies for nondeterministic time, Hard promise problems and nonuniform complexity, Strong nondeterministic Turing reduction - a technique for proving intractability, Probabilistic complexity classes and lowness, AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly, Complete sets and closeness to complexity classes, Qualitative relativizations of complexity classes, The recursion-theoretic structure of complexity classes, Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
Cites Work
- Unnamed Item
- On gamma-reducibility versus polynomial time many-one reducibility
- Reductions on NP and p-selective sets
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- On the Structure of Polynomial Time Reducibility
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Polynomial Time Enumeration Reducibility
- The complexity of theorem-proving procedures
