How to quote passage with literal error that changes the meaning?
If the purpose of quoting the text is to discuss the error, then quote the error. However, in this case, it seems that your purpose is to discuss the real situation. Quoting the error just makes things confusing.  Instead, I suggest something like:


  Wallace et al. [1, p.497] say that polynomial approaches, such as dispatching, "do not work well."1
  
  1 [1, p.497] erroneously described dispatching as nonpolynomial; compare [1,p.495].


The footnote explains that the literal quote from the source is incorrect but attempts to downplay this. The point of the footnote is only to stop the reader being confused if they look up the quote, not to criticize the authors for the mistake. You might be able to phrase the footnote better than I have, to make this point more effectively.

But be sure that it really is an error. The phrasing "Nonpolynomial approaches, like dispatching, may not work well" is ambiguous and could mean any of the following things:


"Nonpolynomial approaches, such as dispatching, may not work well."  (That is, nonpolynomial approaches may not work well; dispatching is an example of a nonpolynomial approach. This is the interpretation that you've used.)
"Nonpolynomial approaches that resemble dispatching may not work well" (That is, among the nonpolynomial approaches, those that resemble dispatching may not work well; other nonpoly approaches might be fine.)
"Nonpolynomial approaches, which resemble dispatching, may not work well." (That is, nonpoly approaches resemble dispatching; nonpoly approaches may not work well.)
"Like dispatching, nonpolynomial approaches may not work well." (That is, dispatching may not work well. Nonpoly approaches have the following commonality with dispatching: they also may not work well."


Also, as dan1111 points out in his answer, you need to be sure that your correction (changing "nonpolynomial" to "polynomial") fixes the error.