Bracketing Discrete Problems by Two Problems of Linear Optimization.

Abstract

Two results are proven: (1) If a certain restricted problem of first-order error analysis in linear programming (specified below), for errors in only the criterion function, has a polynomial-time algorithm, then so does the tautology problem; (2) If the tautology problem is decidable in polynomial time, then linear programs can be solved optimally in polynomial time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1976
Accession Number
ADA032163

Entities

People

  • Robert Jeroslow

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computational Complexity
  • Computer Programming
  • Consistency
  • Error Analysis
  • Errors
  • Inequalities
  • Linear Programming
  • Machines
  • Military Research
  • Optimization
  • Polynomials
  • Rational Numbers
  • Simplex Method
  • Universities

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Mathematical Modeling and Probability Theory.