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)

Review text

Techniques originally developed for establishing NP-completeness are adapted to prove that two compactness theorems concerning hypergraphs are equivalent to the Prime Ideal Theorem for Boolean algebras (BPI). In addition, some possible connections between NP-completeness and BPI are explored.

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)