Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle$ such that:
a) all $\vert v_i \rangle$ are mutually orthogonal
b) there is no product vector orthogonal to all $\vert v_i \rangle$
c) basis is nontrivial, i.e. doesn't span $H$
(such bases are of interest in quantum information)
Is there a polynomial algorithm (in $n$) for finding UPBs? (note that in general there is no upper bound on the size of UPB, so a priori it might be exponential in $n$)
Is there a polynomial algorithm for checking if a given product basis is a UPB? (i.e. is unextendable)
Or is the problem NP-complete?