Exercises marked with (*) require further reading/search beyond the suggested texts.
7. Suppose you have a problem X whose complexity is unknown. You succeed in reducing it to a known NP-complete problem. What can you say about X's complexity?
Answer:
Since we succeed in reducing it to a known NP-complete problem, we can say that X is easier than that NP-complete problem. If X is a decision problem, we can also say that it belongs to NP.
© 2015 Joao Meidanis