_index.org

Spaan 2005

Last edited: August 8, 2025

(Spaan and Vlassis 2005)

Randomized PBVI

One-Liner

PVBI, faster.

Novelty

“Is it necessary to maintain an alpha vector for each belief?”

Notable Methods

Don’t update all beliefs; backup only belief that didn’t yet confer an improvement

Key Figs

New Concepts

Notes

Space Complexity

Last edited: August 8, 2025

We define Space Complexity as the largest tape index reached during computation.

Let \(M\) be a deterministic Turing Machine; the space complexity of \(M\) is the function \(S: \mathbb{N} \to \mathbb{N}\), where \(S(n)\) is the largest number of work tape cells accessed by \(M\) on \(X\); we will consider the input tape as read-only but also it is free (because if we didn’t do this, our space complexity would be trivially \(\geq n\) and that’s kinda lame).

Space Time Hierachy

Last edited: August 8, 2025

I finally get to sound like I’m doing physics.

\begin{equation} L \subseteq P \subseteq \text{PSPACE} \subseteq \text{EXP} \end{equation}

by space hierarchy theorem and time hierarchy theorem, we have also that:

\begin{equation} \text{P} \subset \text{EXP} \end{equation}

and

\begin{equation} L \subset\text{PSPACE} \end{equation}

so we know that one of the subset things on top is a strict subset. There’s also a bridge \(P \subseteq \text{NP} \subseteq \text{PSPACE}\).

\(L =^{?} P\)

We believe that \(L \subset P\), but we can’t show this.

span (linear algebra)

Last edited: August 8, 2025

The span of a bunch of vectors is the set of all linear combinations of that bunch of vectors. We denote it as \(span(v_1, \dots v_{m)}\).

constituents

requirements

\begin{equation} span(v_{1}..v_{m}) = \{a_1v_1+\dots +a_{m}v_{m}:a_1\dots a_{m} \in \mathbb{F}\} \end{equation}

additional information

span is the smallest subspace containing all vectors in the list

Part 1: that a span of a list of vectors is a subspace containing those vectors

spanish

Last edited: August 8, 2025
  1. Órale pues: confirmando
  2. No hay pedo: no hay problema
  3. Ponte la de puebla: dividirlo
  4. Qué padre: sopresa positiva
  5. De a grapa: gratis
  6. De poca madre: júbilo y aceptación
  7. Te vas a dar un ranazo: nos vamos a hacer daño (hurt)

Mamá: ¡necesitamos limpiar sus cuartos! Me: órale pues, no hay pedo. Voy a limpiarlo mañana.

Mi plan está simple. Voy a dividir mi cuarto a media, y contrata mi amiga para ayudarme. ¡Ponte la de puebla!