Incomplete Table Recovery (ITR)
Category: Logic
Input
A collection $F$ of functional dependencies on a finite attribute set $\{A_1, \ldots, A_m\}$, a matrix $T = (T_{ij})$ for $0 \leq i \leq n$ and $1 \leq j \leq m$ called an incomplete table where $T_{0j} = A_j$ for $1 \leq j \leq m$, and the value of each $T_{ij}$ is either a nonnegative integer or the null value $*$ for $1 \leq i \leq n$ and $1 \leq j \leq m$. Refer to [1] for definitions regarding this problem.
Problem
Is $T$ uniquely recoverable under $F$ when the domain of each attribute $A_j$ is the set of nonnegative integers?
Status
$\P$-complete (Miyano and Haraguchi [1], Miyano, Shiraishi, and Shoudai [2]).
Remarks
The reduction to show hardness is from AGAP.
References
- S. Miyano and M. Haraguchi (1982). The computational complexity of incomplete table recovery.
- S. Miyano, S. Shiraishi, and T. Shoudai (1989). A list of P-complete problems.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.6.14.