Search code examples
algorithmbig-ocomplexity-theoryreductionnp

Linear time reduction of languages in class P, complexity implications


I am having problem understanding this topic of P and NP reductions. I understand that if language L1 can be reduced to Language L2 in linear time and L2 is in P, this implies that L1 is in P. But if we know L2 has a time complexity of lets say theta(n log n), can we say that L1 runs in O(n log n)? since the reduction from L1 to L2 is in linear time and L2 runs in theta(n log n) and so it will be O(n) + theta(n log n). And also lets say L2 can be also linearly reduced to L3, we can say L3 runs in omega(n log n)?


Solution

  • tl;dr: Yes. And yes in case you mean big Omega.


    The first part is correct: If you can decide L2 in Theta((n*log(n))) which implies it can be done in O(n*log(n)) and you can reduce L1 to L2 in O(n), then you can also decide for L1 in O(n*log(n)) with exactly the argument you made. (Note: this does not mean, that you can't possibly decide L1 in less than this - there might be an algorithm to solve L1 in O(n). It's only an upper bound...)

    However, the second part is not correct. If you can reduce L2 to L3, then you can say nothing about L3s running time not matter what the running time of the reduction from L2 to L3 is. (Update: this only shows that L3 might be harder, not more) L3 might be a very hard problem, like SAT for instance. It then is very likely that you can reduce L2 to it, i.e. that you can solve L2 with 'rephrasing' (a reduction) the problem + a SAT-solver - still SAT is NP-complete.


    DISCLAIMER: as noted in the comments by DavidRicherby the second part of my answer is wrong as it stands - @ uchman21 you were right, L3 has to be in Omega(n*log(n)) (note the upper case!):

    If we know the complexity of L2 is Theata(n*log(n)) (upper and lower bounds, O(n*log(n)) and Omega(n*log(n))) and we can reduce L2 to L3 in time O(n), then L3 is at least as hard as L2 - because we know there is no algorithm which can solve the problem L2 faster than Omega(n*log(n)). However, if L3 was faster, that is in o(n*log(n)), then the algorithm 'reduction+solve_L3' runs in O(n)+o(n*log(n)) which still is in o(n*log(n)) and it solves L2 - contradiction. Hence, L3 has to be in Omega(n*log(n)).