2
$\begingroup$

I am fascinated by a recent fact I was reading: Succinct Circuits are simple machines used to descibe graphs in exponentially less space, which leads to the downside that solving a problem on that graph, which is NP-complete, is NEXPTIME-complete.

I have two concrete questions:

1) Are there more examples where one can trade an smaller space/memory representation for a slower algorithm? Is there a specific term for this tradeoff?

2) Are there examples where the opposite can be achieved, namely having an exponentially faster algorithm given an exponentially larger encoding of the problem?

Improve this question
$\endgroup$
3
  • $\begingroup$ For 2), if you use unary encoding of numbers, then many NP-complete problems become easy. $\endgroup$
    – Wojowu
    Mar 11, 2019 at 22:12
  • $\begingroup$ That is interesting, is this the same as 1-hot-encoding? Could you give an example hot to use such an encoding trick please? Thank you! $\endgroup$
    – ACGT
    Mar 11, 2019 at 22:14
  • 4
    $\begingroup$ (1) Any time you have a problem which is (class)-hard on a given set of inputs, and the set is sparse, you can boost hardness. If the set is sparse and also you have an efficient way to represent them, this boosting is something you can control (in your example, going from NP to NEXP and not to something even higher). (2) It's called padding, and it's a nice trick to get intermediate or 'tuned' problems from ones which are harder than you wanted. $\endgroup$
    – user36212
    Mar 11, 2019 at 22:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.