The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
80 views
If L1 is polynomial time reducible to L2 , then can this be true that :

If L1 is not in P => L2 will not be in P.
asked in Theory of Computation by (173 points) | 80 views
0
True.
0
how this can be true?
0
Explanation added in Answer. Kindly refer the answer for details.

1 Answer

+3 votes

If L1 is polynomial time reducible to L2 , then can this be true that :

If L1 is not in P => L2 will not be in P.

If L1 is not in P => L2 will not be in P. .. ..Is True.

The easiest way to see why this is True is to change this statement(implication statement) into its contrapositive. 

i.e. If $L2$ is in $P$ then $L1$ will be in $P$.

Since, $L1$ is Polynomial time reducible to $L2$ and Now, If $L2$ is in $P$...then $L1$ will be in $P$.

The Algorithm to solve $L1$ can work like this : Convert Problem $L1$ into $L2$ (Polynomial time) and then Solve $L2$ (Polynomial time)... Hence, We can say $L1$ is Polynomial time problem.



Some Properties to remember :

Let $\rightarrow$ mean "Polynomial time reduction". And $P_i$ be some decision problem.

 If $P1 \rightarrow P2$..(i.e. $P1$ is Polynomial time reducible to $P2$) then If $P1$ is Hard then $P2$ is Hard. 

Or if $P2$ is Easy then $P1$ is easy.

(By Word "Hard", I don't necessarily mean NP-Hard.."Harder" means having a higher estimate of the required computational resources in a given context (e.g., higher time complexity, greater memory requirement, )


Let $\rightarrow$ mean "many-one reduction". And $L_i$ be some language.

If $L1 \rightarrow L2$ then If $L1$ is Undecidable then $L2$ is also Undecidable.

Or if $L2$ is decidable then $L1$ is also decidable.


Though, I would urge aspirants to go in quite depth in this topic in both Complexity classes as well as in TOC...But These Topics are not included in GATE syllabus and students/teachers seem to be skipping these topics. Hence, For such students, Just remembering few results will also work in PSU examinations. And to remember the above results, I have some analogy.

Have you heard a Hindi phrase "बात  का  बतंगड़  बनाना " ... Yes..this phrase suits to the properties above.

बात can go/reduce into "बात or बतंगड़".. (A reduction from one problem to another means that the second problem is at least as difficult as the first.) (Decidable can be reduced into Decidable or Undecidable)

But बतंगड़ can only go into (reduce into) बतंगड़ .. (Undecidable can only be reduced into Undecidable)

answered by Boss (18.7k points)
edited by
0

chk this

 if L1 is the empty language, and L2 is the "full language" {0,1} there does not seem to be a reduction from L2 to L1

https://cs.stackexchange.com/questions/19427/does-two-languages-being-in-p-imply-reduction-to-each-other

0
@Deepakk ,could you please explain what "many-one" denotes in many-one reduction. when we convert instances of one decision problem to other decision problem then we say it is many-one reduction but what is "many" and what is "one" here ?
0

if L1 is the empty language, and L2 is the "full language" {0,1} there does not seem to be a reduction from L2 to L1

Doesn't have to be. All the results in the answer are based on "If there is a reduction then......" 

0
@ankitgupta, I only know the definition of Many-one reduction as you do...hence, Can't explain it in easy words.  Will be surely digging about it as TOC interests me very much.
0
ok no problem and thank you for the response :)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,851 questions
47,514 answers
145,843 comments
62,274 users