scientific article; zbMATH DE number 4002078

MaRDI QIDQ3754606zbMATH OpenFDO

Authors Michael Sipser

Publication date 1986

zbMATH Keywords

analytic setsdescriptive set theory\(NP=co\)-NP question

Mathematics Subject Classification ID

Descriptive set theory (03E15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 3938569
• The complexity of some topological inference problems
• scientific article; zbMATH DE number 5263151
• scientific article; zbMATH DE number 4012593
• A topological approach to non-uniform complexity
• scientific article; zbMATH DE number 16121
• Complexity of some geometric and topological problems
• The computability problem in algebraic topology
• On higher analogs of topological complexity
• Computational complexity of topological invariants

Cited in

(22)

• scientific article; zbMATH DE number 5263151 (Why is no real title available?)
• Local rainbow colorings for various graphs
• Complexity classes as mathematical axioms
• Compatibility matrix method
• RECYCLING RANDOM BITS IN PARALLEL
• Borel separability of the coanalytic Ramsey sets
• Algorithmic complexity of recursive and inductive algorithms
• scientific article; zbMATH DE number 1786653 (Why is no real title available?)
• The expressive power of analog recurrent neural networks on infinite input streams
• scientific article; zbMATH DE number 238404 (Why is no real title available?)
• On locally rainbow colourings
• Topology of cycles in pseudolinear programs
• scientific article; zbMATH DE number 3938569 (Why is no real title available?)
• scientific article; zbMATH DE number 4012593 (Why is no real title available?)
• scientific article; zbMATH DE number 3877163 (Why is no real title available?)
• scientific article; zbMATH DE number 1533816 (Why is no real title available?)
• Proving properties of interactive proofs by a generalized counting technique
• A topological approach to Yablo's paradox
• Formal aspects of topological complexity
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• If not empty, NP-P is topologically large
• Some complexity results in topology and analysis

This page was built for publication:

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