{'fraction_non_alphanumeric': 0.018067556952081697, 'fraction_numerical': 0.003142183817753339, 'mean_word_length': 5.275862068965517, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The impact of complexity theory on algorithms for sparse polynomials

In recent work [12][13], Plaisted has considered the computational complexity of certain decision problems for sparse polynomials. The present expository paper is intended to make these results accessible to those working in the area of algebraic manipulation and to clarify the relevance of the results to this area. The basic insight to be gained is that if the best known algorithms for a problem concerning (not necessarily sparse) polynomials process sparse polynomials in such a way that sparsity is lost, then one should not expect it to be possible to design special algorithms with consistently improved performance on sparse polynomials, unless one hopes to solve the NP = P problem positively. Also we note, for the sake of improved communication between complexity theorists and those working on algebraic manipulation, that there is a significant difference between the conventions used for expressing computation time in the two areas: Many algorithms which always run within a polynomial number of steps, in terms of the algebraic parameters involved, will require an exponential number of steps, in terms of input length (as is the usage in complexity theory), on infinitely many inputs.