Seed Problem Solution – Intro to Theoretical Computer Science


And the answer here is that all 3 statements are actually correct. So the strongest one is probably this one here, so if you just happen to show just one single NP complete problem to be solvable in polynomial time, then all NP complete problems are solvable in polynomial time on a deterministic RAM, so on your home computer, basically. If all NP complete problems are solvable in polynomial time, because they are NP complete that also means, of course, that all problems that are an NP are solvable in polynomial time. So this one here is true, as well. Some problems in NP can be solved in polynomial time, yeah. We already know that, and actually, that’s the weakest of the 3 statements, so if all problems are solvable in polynomial time, yes, some problems are solvable in polynomial time.

Leave a Reply

Your email address will not be published. Required fields are marked *