The enumerability of P collapses P to NC

DOI10.1016/J.TCS.2005.07.010MaRDI QIDQ2575747zbMATH OpenOpenAlexFDO

Authors Alina Beygelzimer, Ogihara, Mitsunori

Publication date 6 December 2005

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

Full work available at URL https://doi.org/10.1016/j.tcs.2005.07.010

zbMATH Keywords

Circuit value problemComplexity theoryEnumerative approximations

Mathematics Subject Classification ID

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

Recommendations

• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 1559536
• On the Average Case Complexity of Some P-complete Problems
• Enumerative counting is hard
• scientific article; zbMATH DE number 1114018

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• A note on enumerative counting
• A taxonomy of problems with fast parallel algorithms
• Approximable sets
• Boolean circuits versus arithmetic circuits
• Enumerative counting is hard
• Fast parallel matrix and GCD computations
• scientific article; zbMATH DE number 429512 (Why is no real title available?)
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 1250549 (Why is no real title available?)
• scientific article; zbMATH DE number 1332674 (Why is no real title available?)
• scientific article; zbMATH DE number 607286 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Inverting a Vandermonde matrix in minimum parallel time
• Modern computer algebra
• On membership comparable sets
• On the complexity of ranking
• On the density of families of sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On uniform circuit complexity
• Parallel Algorithms for Algebraic Problems
• Polynomial-Time Membership Comparable Sets
• Reconstructing Algebraic Functions from Mixed Data
• Relativized circuit complexity
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• Tally NP sets and easy census functions.
• The (Non)enumerability of the determinant and the rank
• Very Fast Parallel Polynomial Arithmetic

Cited in

(1)

• Mathematical Foundations of Computer Science 2004

This page was built for publication: The enumerability of P collapses P to NC

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