Can you substitute physical storage with time complexity?

Question

Inspiration:

Each proper Sudoku puzzle has only one solution. In the unsolved state, values are omitted. By solving the puzzle, one obtains these values. One can solve the puzzle as intended, or theoretically brute force the solution so that the Sudoku property is held. Could this also be applied to data compression?

Approach:

Instead of looking for patterns in the data, can you create a sufficient description with rules that allow only one solution? Hash functions used for fingerprinting files could be one such rule. But if the data is large, collisions occur in the output of the hash function. Is it possible to construct/find a composition of rules that define a unique solution while being smaller then the original file? If you can find such a rule, you could include the number of bits of the original file and brute-force validate the rule on all permutations of these bits.

Answer 1

No, this is not valid. You're not really understanding what lossless data compression is.

For any given length n, there number of byte sequences that are n-bytes long or less is about 256ⁿ.

The number of shorter sequences is simply less, so no lossless compressor can find a compressed representation for every file.

The goal of a compressor is to assign the shortest possible output sequences to the most likely input sequences. (The relative number of meaningfully shorter sequences is actually very small.) For every input that it actually compresses, there must be another input that it expands.

Any valid lossless compressor is therefore based on a statistical model that predicts which inputs are more likely. You are not making any attempt to model the likelihood of various inputs, so the it's not just the resulting idea that's invalid. The whole way of thinking about the problem is invalid.