We study the complexity of constructing an optimal parsing φ of a string s = s 1 … s n under the constraint that given a position p in the original text, and the LZ76-like (Lempel Ziv 76) encoding of T based on φ , it is possible to identify/decompress the character s p by performing at most c accesses to the LZ encoding, for a given integer c . We refer to such a parsing φ as a c -bounded access LZ parsing or c -BLZ parsing of s . We show that for any constant c the problem of computing the optimal c -BLZ parsing of a string, i.e., the one with the minimum number of phrases, is NP -hard and also APX -hard, i.e., no P T A S can exist under the standard complexity assumption P ≠ N P . We also study the ratio between the sizes of an optimal c -BLZ parsing of a string s and an optimal LZ76 parsing of s (which can be greedily computed in polynomial time). For this we establish a non-trivial lower bound Ω ( | s | c + 1 ) on the size of an optimal parsing for a square free string s , and also show that such a lower bound is tight for a large class of (square free) morphic words. Finally, after showing that under ETH, every algorithm for c -BLZ requires time 2 Ω ( | s | 1 c ) , hence strongly exponential in the special case c = 1 , we show an algorithm matching this bound that can compute an optimal 1-BLZ parsing of a string s in time ⁎ O ⁎ ( 1.755 | s | ) .