# Tag Info

9

Thanks to my colleague Maxim Zhukovskii for suggesting this answer. It turns out that the answer is negative, and the counterexample is rather simple. Just take $G=K_m\sqcup \overline{K_m}$ and $H=K_{m+1}\sqcup \overline{K_{m-1}}$ for $n=2m$ and $G=K_m\sqcup \overline{K_{m+1}}$ and $H=K_{m+1}\sqcup \overline{K_m}$ for $n=2m+1$. (Here $K_s$ is an $s$-clique ...

6

Snir has proved a tight lower bound on the size of monotone formulas representing the permanent of an $n\times n$ matrix. The lower bound is $2^{2n - 0.25\log^2 n}$, and he notes that a formula of size $2^{2n - 0.25\log^2 n + O(\log n)}$ exists (Theorem 3.1. and comment after the proof). The survey by Shpilka, and Yehudayoff is a good resource. Also, a ...

5

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with polynomial formula size [Ben-Or and Cleve]. (For $m=2$, it is not as powerful [Allender and Wang]). [Update: As far as I know, this is only true for iterated ...

4

As Kyle Jones has mentioned, the example you provided is called (restricted) resolution. Beside that, pure literals can also be safely removed from a SAT problem. Unit clauses can be assigned a truth value. Check this paper: The Puzzling Role of Simplification in Propositional Satisfiability. Inês Lynce and João Marques-Silva. It discusses several ...

1

These things are called variable and literal (in)dependence. To check that a literal/variable is dependent is in NP [1]. [1] Propositional Independence - Formula-Variable Independence and Forgetting. available at arxiv

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