Two hypergraph theorems equivalent to BPI

DOI10.1305/NDJFL/1093635418MaRDI QIDQ920087zbMATH OpenOpenAlexWikidataFDO

Authors Robert Cowen

Publication date 1990

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1093635418

zbMATH Keywords

Boolean algebrascompactnesshypergraphsNP-completenessPrime Ideal Theorem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other classical set theory (including functions, relations, and set algebra) (03E20) Hypergraphs (05C65)

Recommendations

• scientific article; zbMATH DE number 1885963
• Restricted versions of the Tukey-Teichmüller theorem that are equivalent to the Boolean prime ideal theorem
• scientific article; zbMATH DE number 517057
• scientific article; zbMATH DE number 1416397
• BPI is equivalent to compactness-n, n 6, of Tychonoff powers of 2

Cited in

(8)

• 2-cnfs and logical embeddings
• Satisfiability on hypergraphs
• A 2-isomorphism theorem for hypergraphs
• Borsuk's partition problem and finite point sets
• scientific article; zbMATH DE number 1303454 (Why is no real title available?)
• scientific article; zbMATH DE number 517057 (Why is no real title available?)
• scientific article; zbMATH DE number 1885963 (Why is no real title available?)
• scientific article; zbMATH DE number 1416397 (Why is no real title available?)

This page was built for publication: Two hypergraph theorems equivalent to BPI

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