12

The question you are asking is equivalent to unary NP = unary P, which in turn is equivalent to NE = E, by padding. From the title, perhaps you meant to ask if it is possible to generate input/output pairs such that the distribution on the inputs is "hard." The possibility of doing this lies somewhere between P $\ne$ NP and one-way functions exist. In ...


8

Here are answers to your last two questions. (5) Sorting networks are uniform circuits that sort as fast as the best RAM algorithms, but are definitely not just conversions of RAM algorithms (e.g. quicksort). [AKS83,G14] (4) Yes, for any $s(n)=(1+\varepsilon) \cdot 2^n/n$ with $\varepsilon>0$, but for a silly reason: Every function is computed by a ...


6

Like Emil says, the answer is yes, because the length (in binary) of the input string is actually computable by a deterministic logtime Turing machine, so is a fortiori in $\mathsf{FO}$. You may find this stated as Lemma 13 of Buss's The Boolean formula value problem is in ALOGTIME. The idea, attributed to Dowd, is to use the query tape to do binary search ...


4

Question: Let $M\in \mathsf{PF}$ generate formulas. Does $\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ belong to $\mathsf{P}$? $succinctSAT \in \mathsf{E} \implies$ Yes: The assumption about the generation of the formulas in polynomial time from $1^n$ means that the formula can be succinctly given. You want to decide their satisfiability in time $n^...


4

Regarding your last question: The paper Size-Depth Trade-offs for Threshold Circuits shows that the parity function requires depth-$d$ threshold circuits with $\ge n^{1+\epsilon(d)}$ wires, which is tight up to the function $\epsilon$. But for gates not even $\Omega(n)$ lower bounds are known.


3

Not sure about what kind of results you seek but here what I know for sub-classes of $AC^0$ (constant depth and polynomial size Boolean circuits): The separation between $AC^0$ and its linear fragment (namely $LAC^0$) is known since 96. It is a result of Chaudhuri and Radhakrishnan : "Deterministic restrictions in circuit complexity". This result seems to ...


Only top voted, non community-wiki answers of a minimum length are eligible