QUALITATIVE Matrices: Strong Sign-Solvability and Weak Satisfiability.

Abstract

The study of 'qualitative' linear systems was suggested by Paul Samuelson in 1947 in his influential book on Foundations of Economic Analysis. The present paper deals with a rather general form of qualitative solvability, of which strong sign-solvability is a special case, and with a closely related notion, weak satisfiability, from propositional logic. The study of strong sign-solvability is reduced to that of s-matrices and a conjecture of T. Gorman on the structure of S-matrices is elucidated. An algorithm is described which uses linear programming methods to recognize S-matrices (and much more general systems) and thus solves this recognition problem is polynomial time. However, this is close to the boundary of NP-completeness, for the closely related problem of recognizing weak satisfiability is shown to be NP-complete. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1980
Accession Number
ADA087686

Entities

People

  • Richard Ladner
  • Victor Klee

Organizations

  • University of Washington

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Coding
  • Computations
  • Construction
  • Economic Analysis
  • Inequalities
  • Linear Programming
  • Linear Systems
  • Logic
  • Numbers
  • Polynomials
  • Real Numbers
  • Recognition
  • Sequences
  • Simplex Method
  • Theorems
  • United States Government

Readers

  • Mathematical Modeling and Probability Theory.
  • Operations Research
  • Theoretical Analysis.