All Questions
5 questions
3
votes
1
answer
69
views
Circuit size of a random two to one function
Consider the set of all possible two-to-one functions that map inputs from $\{0, 1\}^{n}$ (domain) to outputs in $\{0, 1\}^{m}$ (co-domain) and let $m > n$.
If I pick a function randomly from this ...
- 249
1
vote
1
answer
123
views
What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?
If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
- 111
0
votes
0
answers
55
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?
- 83
8
votes
1
answer
3k
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$
- 1,165
1
vote
1
answer
152
views
Polynomial Identity Testing Evaluating a polynomial on a circuit
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 ...
- 161