StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POIs this "Valid mathematical expression" problem P, or NP?
text
Body
copied!<p>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?</p> <p>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)? </p> <p>An example will should clarify any questions:</p> <p>given: {2, 3, 5, 25} , {+, -, *, /} , {=}<br> output: YES</p> <p>the expression (only one i think) is (2 + 3) * 5 = 25. you only need to output YES/NO.</p> <p>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. </p> <p>a. non-deterministically select a sequence of operators to place between the integers.<br> b. verify you answer is a valid mathematical expression (this can be done in constant time). </p> <p>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)</p> <p>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 :)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload