# All Questions

6 questions
25 views

### Is the succinct version of P-complete problems out of P?

Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
46 views

### Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
391 views

### Isn't polynomial identity testing over arithmetic *expressions* trivial?

Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
1k views

### What is the decidable language in $P/poly$ but not in $P$?

Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$
Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of ...