I was wondering if a computational problem exists with the following properties:
- It should be solvable only having $K$ bytes of memory, or solvable with $K' < K$ bytes of memory only in exponential time on $K - K'$ (or such an high degree polynomial in $K - K'$ that for any practical purpose the computation is unfeasible).
- The input to the problem should not be bigger than $O(\ln(K))$.
- The output to the problem should not be bigger than $O(\ln(K))$.
- The time complexity of the problem should be less or equal than $O(K \ln (K))$.
I have thought of many possible solutions but could always find a counterexample. Any sub-optimal suggestion or pointer is also very appreciated.