Why it is computationally harder to reconstruct the past than to predict the future
type: Item
instance of: scholarly article
title: Why it is computationally harder to reconstruct the past than to predict the future
zbMATH Open document ID: 0885.65047
DOI: 10.1007/BF02435838
author: Misha Koshelev
author: Gotz Alefeld
author: Günter Mayer
published in: International Journal of Theoretical Physics
publication date: 1998-04-02T00:00:00Z
review text: This paper brings nothing new except a kind of physical interpretation of recent results concerning NP-hardness of computing exact bounds on solutions of linear interval equations. Considering the relationship between the vector of state variables \(x\) and the vector of ``future'' values \(y\) in the linear form \(y=Ax\), and assuming interval uncertainty of data, the authors obtain the results claimed in the title from the facts that given interval \(x\), computing \(y\) is polynomial-time whereas given interval \(y\), computing \(x\) is NP-hard.
reviewed by: Jiří Rohn
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65G30
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 1098517
zbMATH Keywords: linear interval equations
zbMATH Keywords: NP-hardness
zbMATH Keywords: exact bounds on solutions
MaRDI profile type: MaRDI publication profile
cites work: Q4209098
cites work: Q4874514
cites work: On the Shape of the Symmetric, Persymmetric, and Skew-Symmetric Solution Set
cites work: The Shape of the Solution Set for Systems of Interval Linear Equations with Dependent Coefficients
cites work: Q3619797
cites work: Q4874512
cites work: Q4851401
cites work: Approximate linear algebra is intractable
cites work: Q4885382
cites work: NP-hard classes of linear algebraic systems with uncertainties
cites work: Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
cites work: Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
full work available at URL: https://doi.org/10.1007/bf02435838
OpenAlex ID: W2045461672
Recommended article: Prediction, retrodiction, and the amount of information stored in the present
Recommended article: Algorithmic complexity bounds on future prediction errors
Recommended article: Predicting the future. Completing models of observed complex systems
Recommended article: Efficient computing procedures and impossibility to solve the problem of exact prediction of events in the quantum world
Recommended article: Reversibility and Predictions
Recommended article: Q4737140
Recommended article: On the ``prediction'' problem
Recommended article: Q3144780
Recommended article: Predictability, complexity, and learning
description: scientific article; zbMATH DE number 1098517