NP-completeness of Partial Chirotope Extendibility

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

In 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.
4 pages

Keywords

Combinatorics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/74970

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0504430
 http://arxiv.org/abs/math/0504430

Collections

arXiv