Inverting An NC⁰ Permutation (InvNC0Perm)
Category: Circuit Complexity
Input
An $n$-input, $n$-output $\NC^0$ circuit computing a bijective function $f : \{0, 1\}^n \to \{0, 1\}^n$ and $y \in \{0, 1\}^n$.
Problem
Is the last bit of $f^{-1}(y)$ equal to 1?
Definitions
See CVP.
Status
$\P$-hard (Håstad [1, Section 2.5], [2]).
Remarks
The reduction to show hardness is from CVP. This problem is called straight-line program in [2]. The problem is not known to be in $\P$ in general, although the family of permutations used to show $\P$-hardness is polynomial time invertible. See Boppana and Lagarias [3] for some additional remarks about one-way functions.
References
- J. H˚astad (1987). Computational Limitations of Small-Depth Circuits.
- J. H˚astad (1987). One-way permutations in NC 0.
- R. B. Boppana and J. C. Lagarias (1986). One way functions and circuit complexity.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.1.12.