Cheap and Secure Web Hosting Provider : See Now

[Answers] How to prove that this is NP complete?

, , No Comments
Problem Detail: 

I'm trying to prove that if P = NP, then {⟨a, b, c⟩ : a + b = c} (as addition over N) is NP-complete.

I think I managed to prove that it is in NP, but I'm not sure what would be a good NP complete problem to reduce to would be, or what algorithm to use. Any ideas?

Asked By : Matthew Aldridge

Answered By : Yuval Filmus

Your language is in P; try to figure out why. If P=NP, all non-trivial languages in P are NP-complete, and in particular this one.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33496

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback