Q1. True: {2, 3, 4, 5, 8}, Not True: {9}, (Unknown: {1, 6, 7}) Since FF is a search problem, this means it is in NP, and since we can reduce 3-COL to FF, it must be NP-Hard; these two combined tells us that FF is NP-Complete. While reductions are not symmetric, it happens that any problem in NP can be reduced to an NP-complete problem like 3-COL. If problem A (3-COL) can be reduced to B (FF), and we can solve B (FF) in polynomial time, then we can solve A (3-COL) in polynomial time. FF is NP-complete, so we do not know if we can solve it in polynomial time or not (this is the P = NP conjecture). However, we can definitely solve any problem in NP in exponential time. Q2. Yes, it does. It implies that P != NP, which in turn implies that no NP-complete problem has a polynomial-time algorithm. For instance, there is no polynomial-time algorithm for 3-COLORING, or for 3-SAT, or for the Traveling Salesman Problem, or ... It doesn't matter whether RILP, is NP-complete or not; the reasoning above holds either way. You don't need to know whether other problems can be reduced to it; the reasoning above holds either way.