# The Relationship Between L, NL, P, and NP

Page 1 of 1

## 1 Replies - 1378 Views - Last Post: 12 October 2012 - 09:24 AM

### #1 JTHM

Reputation: 0
• Posts: 11
• Joined: 25-April 12

# The Relationship Between L, NL, P, and NP

Posted 12 October 2012 - 07:38 AM

I have some questions about the P?=NP and the L?=NL problems:

If L=NL, would that entail P=NP?
If L!=NL, would that entail P!=NP?

Citations would be helpful, if you have them.

Is This A Good Question/Topic? 0

## Replies To: The Relationship Between L, NL, P, and NP

### #2 mojo666

Reputation: 233
• Posts: 549
• Joined: 27-June 09

## Re: The Relationship Between L, NL, P, and NP

Posted 12 October 2012 - 09:24 AM

No. We know NP contains P which contains NL which contains L. even if you prove that L=NL it is still possible P!=NP.

wiki

EDIT -
If you were to show that L=NP or NL=NP, then that would entail P=NP. To show P!=NP, you would have to show something like NL=P and NL!=NP

This post has been edited by mojo666: 12 October 2012 - 09:34 AM