Completeness for parity problems
From MaRDI portal
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Recommendations
- On the Strong Parrott Completion Problem
- On the complexity of certain completion problems
- Parsimonious computational completeness
- Completeness and weak completeness under polynomial-size circuits
- Completeness and weak completeness under polynomial-size circuits
- scientific article; zbMATH DE number 4011938
- Completeness for nondeterministic complexity classes
- A note on complete problems for complexity classes
- Sufficient completeness and parameterized proofs by induction
- Complexity, decidability and completeness
Cited in
(11)- Some observations on holographic algorithms
- Understanding PPA-completeness
- Valiant's holant theorem and matchgate tensors
- Algorithms for modular counting of roots of multivariate polynomials
- Problem of checking the functional completeness in the class of piecewise parallel functions
- The complexity of computational problems about Nash equilibria in symmetric win-lose games
- Barnette's conjecture through the lens of the Mod_k P complexity classes
- scientific article; zbMATH DE number 19766 (Why is no real title available?)
- Exploiting sparsity for bipartite Hamiltonicity
- Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
- Understanding PPA-completeness
This page was built for publication: Completeness for parity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5716924)