Google
 
Web unafbapune.blogspot.com

Friday, February 15, 2013

 

Only Solvable in Exponential Time

What happens if you show one NP-complete problem to be solvable only in exponential time on a Deterministic RAM ?

Some problems in NP only solvable in exponential time
All NP-complete problems only solvable in exponential time
All problems in NP only solvable in exponential time

Which one(s) of the above are true ?

See Unit 2.5 at Intro to Theoretical Computer Science.


Comments: Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?