Timeline for Relation between logspace-uniform circuits and P-uniform circuits
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 23, 2014 at 12:48 | vote | accept | JohnnyCache | ||
| Mar 22, 2014 at 3:21 | answer | added | Yuval Filmus | timeline score: 1 | |
| Mar 21, 2014 at 20:12 | comment | added | Yuval Filmus | I guess you're right... it appears that the difference between logspace-uniform and P-uniform is more important for restricted classes of circuits. | |
| Mar 21, 2014 at 13:24 | comment | added | JohnnyCache | @YuvalFilmus: Thanks for the reply! I still don't fully get it though: a P-uniform circuit is generated in polynomial time, how can the result be larger than a polynomial? Could you give me a small example of such a circuit? | |
| Mar 21, 2014 at 13:07 | comment | added | Yuval Filmus | You're right that any logspace-uniform family of circuits has polynomial size, so this qualification doesn't seem to be necessary. On the other hand, the same is not true for P-uniform circuits, which could be superpolynomial in size. | |
| Mar 21, 2014 at 11:33 | review | First posts | |||
| Mar 21, 2014 at 11:47 | |||||
| Mar 21, 2014 at 11:15 | history | asked | JohnnyCache | CC BY-SA 3.0 |