Is this "Valid mathematical expression" problem P, or NP?

Question

This question is purely out of curiosity. I am off school for the summer, and was going to implement an algorithm to solve this just for fun. That led to the above question, how hard is this problem?

The problem: you are given a list of positive integers, a set of mathematical operators and the equal sign(=). can you create a valid mathematical expression using the integers (in the same order) and the operators (any number of times)?

An example will should clarify any questions:

given: {2, 3, 5, 25} , {+, -, *, /} , {=}
output: YES

the expression (only one i think) is (2 + 3) * 5 = 25. you only need to output YES/NO.

I believe the problem is in NP. I say this because it is a decision problem (YES/NO answer) and I can find a non-deterministic poly time algorithm that decides it.

a. non-deterministically select a sequence of operators to place between the integers.
b. verify you answer is a valid mathematical expression (this can be done in constant time).

In this case, the big question is this: Is the problem in P? (i.e. Is there a deterministic poly time algorithm that decides it?) OR Is the problem NP complete? (i.e. Can a known NP Complete problem be reduced to this? or equivalently Is every NP language poly time reducable to this problem?) OR neither? (i.e. problem in NP but not NP Complete)

Note: This problem statement assumes P not equal to NP. Also, although I am new to Stack Overflow, I am familiar with the homework tag. This is indeed just curiosity, not homework :)

Answer 1

An straightforward reduction from the Partition problem (which is NP-Complete) - given a set of N integers S, the input to the "Valid Math" problem would be - the elements of S, N-2 '+' operators and an '=' sign.