www.GetXFactor.com

Leading Technology, Science,
Agriculture News and information
Part of the Identityscape.com network...

getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

 

 

P vs. DSPACE(n)
   Science and Technology news... Forum Index -> Cryptography Forum  
View previous topic :: View next topic  
Author Message
Guest
PostPosted: Mon Oct 06, 2008 6:37 pm    Post subject: P vs. DSPACE(n) Reply with quote
What is the relationship between P and DSPACE(n)? I think they are
noncomparable but I can>t seem to prove it.
Back to top
Jens Mander
Guest
PostPosted: Tue Oct 07, 2008 2:26 pm    Post subject: Re: P vs. DSPACE(n) Reply with quote
<crystallic_chrome@hotmail.com> schrieb im Newsbeitrag
news:d869e689-0d63-4c3d-8635-1e2eb91ea04d@v72g2000hsv.googlegroups.com...
[quote]What is the relationship between P and DSPACE(n)? I think they are
noncomparable but I can>t seem to prove it.
[/quote]
They are different because P is closed under polynomial time reducibility
whereas DSPACE(n) is not closed.
If one of them is a subset of the other is an open problem in computational
complexity.
Back to top
Display posts from previous:   
   Science and Technology news... Forum Index -> Cryptography Forum  
Page 1 of 1
All times are GMT

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum