#P-COMPLETENESS VIA MANY-ONE REDUCTIONS

DOI10.1142/S0129054191000066zbMath0739.68036OpenAlexW2093869254MaRDI QIDQ3988836

Viktória Zankó

Publication date: 28 June 1992

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054191000066

zbMATH Keywords

reducibilitycountingpermanent

Mathematics Subject Classification ID

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

Related Items (18)

Nondeterministic functions and the existence of optimal proof systems ⋮ A Dichotomy Theorem for Polynomial Evaluation ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes ⋮ The complexity of problems for quantified constraints ⋮ Unnamed Item ⋮ The consequences of eliminating NP solutions ⋮ On the hardness of counting problems of complete mappings. ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Arithmetization: A new method in structural complexity theory ⋮ On the autoreducibility of functions ⋮ The complexity of power-index comparison ⋮ Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs ⋮ Subtractive reductions and complete problems for counting complexity classes ⋮ SELF-SPECIFYING MACHINES ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

This page was built for publication:

1. P-COMPLETENESS VIA MANY-ONE REDUCTIONS