So I was wondering whether you could always have a multivariate polynomial $P$ over $\mathbb{Z}$ that ...

  • can be represented by arithmetic circuits of size $s$
  • has polynomial degree and exponentially bounded coefficients (so $P$ is computable in polynomial time on some input)
  • which is not computable by circuits of size $s-1$?
  • is not a constant

for any $s$.

I do not need to be able to find such polynomials quickly, I guess this would be very hard task. Actually, I would just like to know if these exist.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy