Vandermonde Matrices, NP-Completeness, and Transversal Subspaces
Résumé
Let E be a vector space of dimension n over an infinite field K. We give polynomial time constructions of families of r-dimensional subspaces of E with the following transversality property: any linear subspace of E of dimension n-r is transversal to at least one element of the family. We also give a new NP-completeness proof for the following problem: given two integers n and m (m bigger than n) and a n times m matrix A with integer entries, decide whether there exists a n times n sub-determinant of A which is equal to zero.
Soit K un corps infini. Nous construisons en temps polynomial des familles de sous-espaces de dimension r de Kn satisfaisant la propriété suivante: tout sous-espace de dimension n−r de Kn est supplémentaire à au moins l’un des membres de la famille. Nous donnons également une nouvelle preuve de NPcomplétude pour le problème suivant: étant donnés deux entiers n et m tels que nxm, et une matrice A de taille nxm à coefficients entiers, décider s’il existe un sous-déterminant nxn de A qui est égal à zéro.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...