Displaying similar documents to “The intrinsic complexity of parametric elimination methods.”

Polynomially Bounded Sequences and Polynomial Sequences

Hiroyuki Okazaki, Yuichi Futa (2015)

Formalized Mathematics

Similarity:

In this article, we formalize polynomially bounded sequences that plays an important role in computational complexity theory. Class P is a fundamental computational complexity class that contains all polynomial-time decision problems [11], [12]. It takes polynomially bounded amount of computation time to solve polynomial-time decision problems by the deterministic Turing machine. Moreover we formalize polynomial sequences [5].

Combinatorial Nullstellensatz approach to polynomial expansion

Fedor Petrov (2014)

Acta Arithmetica

Similarity:

Applying techniques similar to Combinatorial Nullstellensatz we prove a lower estimate of |f(A,B)| for finite subsets A, B of a field, and a polynomial f(x,y) of the form f(x,y) = g(x) + yh(x), where the degree of g is greater than that of h.