scientific article; zbMATH DE number 3938569

MaRDI QIDQ3709896zbMATH OpenFDO

Authors Michael Sipser

Publication date 1984

zbMATH Keywords

analytic setscircuit complexitycomplementNP sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Descriptive set theory (03E15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4002078
• Descriptive set theory and Boolean complexity theory
• If not empty, NP-P is topologically large
• scientific article; zbMATH DE number 1786653
• scientific article; zbMATH DE number 4012593

Cited in

(14)

• A topological approach to Yablo's paradox
• The quantifier structure of sentences that characterize nondeterministic time complexity
• Topology of cycles in pseudolinear programs
• Formal aspects of topological complexity
• scientific article; zbMATH DE number 4002078 (Why is no real title available?)
• scientific article; zbMATH DE number 4012593 (Why is no real title available?)
• Descriptive set theory and Boolean complexity theory
• Some complexity results in topology and analysis
• scientific article; zbMATH DE number 1786653 (Why is no real title available?)
• scientific article; zbMATH DE number 1355469 (Why is no real title available?)
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• scientific article; zbMATH DE number 5263151 (Why is no real title available?)
• Extending the reach of the point-to-set principle
• The regular languages of first-order logic with one alternation

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 Q3709896)