2016/02/01 by Jaroslav Horáček, Horáček, Jaroslav, Milan Hladík +3
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Numerical Methods and Algorithms #Polynomial and algebraic computation #cs.CC
paper · pdf · doi:10.48550/arxiv.1602.00349
Submitted to Mat Triad 2015
arxiv created 2016/02/01 · openalex publication_date 2016/02/01 · arxiv updated 2016/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work connects two mathematical fields - computational complexity and interval linear algebra. It introduces the basic topics of interval linear algebra - regularity and singularity, full column rank, solving a linear system, deciding solvability of a linear system, computing inverse matrix, eigenvalues, checking positive (semi)definiteness or stability. We discuss these problems and relations between them from the view of computational complexity. Many problems in interval linear algebra are intractable, hence we emphasize subclasses of these problems that are easily solvable or decidable. The aim of this work is to provide a basic insight into this field and to provide materials for further reading and research.