Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
The computational complexity of some problems of linear algebra
Extended abstract
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 1200/1997 |
| Book | STACS 97 |
| DOI | 10.1007/BFb0023443 |
| Copyright | 1997 |
| ISBN | 978-3-540-62616-9 |
| Category | Complexity Theory III |
| DOI | 10.1007/BFb0023480 |
| Pages | 451-462 |
| Subject Collection | Computer Science |
| SpringerLink Date | Monday, April 10, 2006 |
| |
|
Complexity Theory III
The computational complexity of some problems of linear algebra Extended abstract
Jonathan F. Buss1  , Gudmund S. Frandsen2 and Jeffrey O. Shallit1
| (1) |
Department of Computer Science, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada |
| (2) |
BRICS, Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000 Aarhus C, Denmark |
Abstract
In this paper we consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let x
1, x
2, ..., x
t
be variables. Given a matrix M= M( x
1, x
2, ..., x
t
) with entries chosen from E  {x
1, x
2, ..., x
t
}, we want to determine and
There are also variants of these problems that specify more about the structure of M, or instead of asking for the minimum or maximum rank, ask if there is some substitution of the variables that makes the matrix invertible or noninvertible.
Depending on E, S, and on which variant is studied, the complexity of these problems can range from polynomial-time solvable to random polynomial-time solvable to NP-complete to PSPACE-solvable to unsolvable.
Supported in part by grants from NSERC Canada.
Supported in part by the ESPRIT Long Term Research Programme of the EU under project number 20244 (ALCOM-IT) and by BRICS, Basic Research in Computer Science, Centre of the Danish National Research Foundation.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|