Interesting.. It's somehow tough for me to accept that a "NP complete" problem can be solved with a regular language.
You construct a DFA. Your start state has (string of toy length) transitions to every possible toy. Then these toys all have self edges looping to themselves (with a string of length toy), and edges to every other toy (with those edges being the length of the other toy)...
But what is your accepting state, do you have 2 "escape" transitions of "toy cost" and "other toy cost" from "toy" to a terminating, accepting state? (Does that work?)
It feels like an abuse of regular languages and automata, and I'm not sure it works...
This is like saying: the balanced parentheses problem can be solved by a regular language, *if you fix the balanced parentheses problem to strings of 2^5 length, and build a machine that accepts all balanced parentheses combinations of 2^5 length. Like yeah, you could hack together an automata to recognize all 2^5 strings, but is it a proper automata at that point?
This is a pseudopolynomial time algorithm: polynomial in the magnitude of an important number, not in the number of bits that it takes to write it down. Problems with those kind of algorithm available don't make P=NP because the problems that don't have known pseudopolynomial solutions, when reduced to problems that do, end up with numbers with logs (rather than magnitudes) polynomial in the size of the original problem.
In real life, numbers are often of human scale (rather than the kind you get from reducing a hard SAT instance to knapsack) and a pseudopolynomial algorithm is great.
Every state that means "a full toy has just been scanned" is a valid accepting state. In fact you don't need separate states for each toy, you only need self-loop of appropriate length.
(Also, this is an NFA, not a DFA)
The language of valid parentheses up to size 2^5 is obviously regular, it's even finite.
You construct a DFA. Your start state has (string of toy length) transitions to every possible toy. Then these toys all have self edges looping to themselves (with a string of length toy), and edges to every other toy (with those edges being the length of the other toy)...
But what is your accepting state, do you have 2 "escape" transitions of "toy cost" and "other toy cost" from "toy" to a terminating, accepting state? (Does that work?)
It feels like an abuse of regular languages and automata, and I'm not sure it works...
This is like saying: the balanced parentheses problem can be solved by a regular language, *if you fix the balanced parentheses problem to strings of 2^5 length, and build a machine that accepts all balanced parentheses combinations of 2^5 length. Like yeah, you could hack together an automata to recognize all 2^5 strings, but is it a proper automata at that point?