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.

  • $\begingroup$ The first constraint is quite weird. It is not usual to look at any complexity measure and count exact units. We usually allow for constants. What I suspect you might mean is that there is an $O(K)$-space $O(K \log K)$-time algorithm and any algorithm that uses $o(K)$ space runs necessarily in $\omega(2^K)$ time. On another note, I suggest editing the question by using $n = \log K$ and making all $K$s $2^n$ where n is the size of the input. Your explanation would be easier to read. $\endgroup$ – aelguindy Oct 24 '16 at 18:49
  • $\begingroup$ "less or equal than O(K ln(K))" -- that doesn't make any sense. You want to just say "in O(K ln K)". $\endgroup$ – Raphael Oct 24 '16 at 22:57
  • $\begingroup$ So we're talking EXPSPACE and EXPTIME territory here? $\endgroup$ – Raphael Oct 24 '16 at 22:58

This kind of question is studied in the cryptography literature under the name "memory-bound computation" or "memory-hard function". Such a function is one that can be computed efficiently using $K$ bytes of memory but takes much longer to compute if you have significantly less than $K$ bytes of memory. So, I suggest that you take a look at cryptographic constructions for memory-hard functions. It's an active area of research, and researchers focus more on practical complexity (concrete running time, not asymptotic running time) than on complexity theory, but you might find it useful.

See https://en.wikipedia.org/wiki/Memory_bound_function#Using_memory_bound_functions_to_prevent_spam for a high-level overview.

  • $\begingroup$ This is more or less exactly what I was looking for. Thank you! $\endgroup$ – Matteo Monti Oct 25 '16 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.