## Abstract

This paper investigates the complexity of computing the minimum mean square prediction error for wide-sense stationary stochastic processes. It is shown that if the spectral density of the stationary process is a strictly positive, computable continuous function then the minimum mean square error (MMSE) is always a computable number. Nevertheless, we also show that the computation of the MMSE is a #P1 complete problem on the set of strictly positive, polynomial-time computable, continuous spectral densities. This means that if, as widely assumed, FP1 ≠ #P1, then there exist strictly positive, polynomial-time computable continuous spectral densities for which the computation of the MMSE is not polynomial-time computable. These results show in particular that under the widely accepted assumptions of complexity theory, the computation of the MMSE is generally much harder than an NP1 complete problem.

Original language | English (US) |
---|---|

Pages (from-to) | 6627-6638 |

Number of pages | 12 |

Journal | IEEE Transactions on Information Theory |

Volume | 70 |

Issue number | 9 |

DOIs | |

State | Published - 2024 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Information Systems
- Computer Science Applications
- Library and Information Sciences

## Keywords

- complexity blowup
- complexity theory
- computability
- minimum mean square error
- Turing machine
- Wiener prediction filter