The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 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.

+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)

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

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......"

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,157 questions

43,608 answers

123,961 comments

42,860 users