Two hypergraph theorems equivalent to BPI
type: Item
instance of: scholarly article
title: Two hypergraph theorems equivalent to BPI
zbMATH Open document ID: 0708.03024
author: Robert Cowen
published in: Notre Dame Journal of Formal Logic
publication date: 1990-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 03E20
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4162871
zbMATH Keywords: NP-completeness
zbMATH Keywords: compactness
zbMATH Keywords: hypergraphs
zbMATH Keywords: Prime Ideal Theorem
zbMATH Keywords: Boolean algebras
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1093635418
OpenAlex ID: W2006078799
Wikidata QID: Q60680295
DOI: 10.1305/NDJFL/1093635418
description: scientific article; zbMATH DE number 4162871