NP-completeness of Partial Chirotope Extendibility

Simple item page
dc.creatorBaier, Patrick
dc.date2005-04-21
dc.date.accessioned2026-07-07T05:19:18Z
dc.date.available2026-07-07T05:19:18Z
dc.descriptionIn the monograph "Axioms and Hulls" (1992) Donald Knuth studies some axiomatizations of geometric situations. The structures described by one of the axiom systems are called CC-systems. Knuth proves that it is NP-complete to decide, whether a partially defined CC-system can be extended to a complete CC-system. The aim of this note is to show that Knuth's proof of this result also implies that it is NP-complete to decide the extendability of partially defined chirotopes.
dc.description4 pages
dc.identifierhttps://arxiv.org/abs/math/0504430
dc.identifierhttp://arxiv.org/abs/math/0504430
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/74970
dc.subjectCombinatorics
dc.titleNP-completeness of Partial Chirotope Extendibility
dc.typetext

Files

Collections

arXiv