Relations among MOD-classes

DOI10.1016/0304-3975(90)90081-RMaRDI QIDQ914370zbMATH OpenFDO

Authors Ulrich Hertrampf

Publication date 1990

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

Full work available at URL https://doi.org/10.1016/0304-3975(90)90081-R

zbMATH Keywords

deterministic polynomial time computationMod-classesoracle

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A note on Mod and generalised Mod classes
• On the power of generalized Mod-classes
• Counting classes: Thresholds, parity, mods, and fewness
• Representing Boolean functions as polynomials modulo composite numbers
• Counting classes: Thresholds, parity, mods, and fewness

Cites work

• Counting classes: Thresholds, parity, mods, and fewness
• Relativized counting classes: Relations among thresholds, parity, and mods

Cited in

(19)

• Graph isomorphism is low for PP
• Representing Boolean functions as polynomials modulo composite numbers
• On helping by parity-like languages
• Geometric sets of low information content
• Tally NP sets and easy census functions.
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• Barnette's conjecture through the lens of the Mod_k P complexity classes
• scientific article; zbMATH DE number 5929661 (Why is no real title available?)
• On the power of generalized Mod-classes
• Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
• Counting classes: Thresholds, parity, mods, and fewness
• Semiring reasoning frameworks in AI and their computational complexity
• On the power of counting the total number of computation paths of NPTMs
• A note on Mod and generalised Mod classes
• Modulo classes and logarithmic advice
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• New perspectives on semiring applications to dynamic programming
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Modular counting CSP: reductions and algorithms

This page was built for publication: Relations among MOD-classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q914370)