Why it is computationally harder to reconstruct the past than to predict the future

DOI10.1007/BF02435838MaRDI QIDQ1376490zbMATH OpenOpenAlexFDO

Authors Misha Koshelev, Gotz Alefeld, Günter Mayer

Publication date 2 April 1998

Published in International Journal of Theoretical Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02435838

zbMATH Keywords

exact bounds on solutionslinear interval equationsNP-hardness

Mathematics Subject Classification ID

Interval and finite arithmetic (65G30) Complexity and performance of numerical algorithms (65Y20)

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.

Recommendations

• Prediction, retrodiction, and the amount of information stored in the present
• Algorithmic complexity bounds on future prediction errors
• Predicting the future. Completing models of observed complex systems
• Efficient computing procedures and impossibility to solve the problem of exact prediction of events in the quantum world
• Reversibility and Predictions
• scientific article; zbMATH DE number 2086606
• On the ``prediction problem
• The nature of prediction (and the prediction of nature)
• Predictability, complexity, and learning

Cites work

• Approximate linear algebra is intractable
• Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
• Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1206056 (Why is no real title available?)
• scientific article; zbMATH DE number 804135 (Why is no real title available?)
• scientific article; zbMATH DE number 869736 (Why is no real title available?)
• scientific article; zbMATH DE number 869738 (Why is no real title available?)
• scientific article; zbMATH DE number 903768 (Why is no real title available?)
• NP-hard classes of linear algebraic systems with uncertainties
• On the Shape of the Symmetric, Persymmetric, and Skew-Symmetric Solution Set
• The Shape of the Solution Set for Systems of Interval Linear Equations with Dependent Coefficients

This page was built for publication: Why it is computationally harder to reconstruct the past than to predict the future

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1376490)