Is this an NP problem?

Question

I recently read articles about NP and P. So the problem of finding the combinations of the given word is an NP problem? For example, the given word anto, the result can be anot,toan and so on. As I came to know, whenever we can check the solution for the problem in a polynomial time then it means that it comes under NP. So the problem of combination comes under NP?

This is just to know whether I have understood NP and P very well.

Answer 1

This problem is not in NP because NP consists of decision problems, problems which have a yes or no answer. However, this problem can easily be made into a decision problem by rephrasing it as "given a collection of letters, a dictionary, and some number of words out of that dictionary, is there an anagram of those letters that's in the dictionary but not in the list of words we have so far?"

This problem is definitely solvable in polynomial time (and therefore nondeterministic polynomial time) because you can just iterate across the dictionary checking each possible word, which takes time polynomial in the size of the dictionary and input word. However, that doesn't make it in either P or NP, since you aren't asking a yes/no question.

Hope this helps!

Answer 2

AFAIK I know NP is a decision problem because there isn't a solution to the problem. What's left is often a greedy algorithm or genetic algorithm that may find a good solution in polynominal time. A brute-force is impratical and it is not even sure if it find the optimal solution.