Questions tagged [formulas]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
12
votes
1answer
233 views

For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

I want to be very specific. Does anyone know of a disproof or a proof of the following proposition: $\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$ $\forall G, H \in STRUC[\Sigma_{graph}] (...
6
votes
1answer
213 views

Arithmetic complexity of matrix powering

Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables. We know that size of smallest formula that computes $\mathsf{Tr}(M^d)$ where $d\in\Bbb N$ could be ...
4
votes
3answers
173 views

Remove unneeded atoms in CNF minimalization (SAT preprocessing)

This might be a very basic question. I am interested in all atoms of a propositional formula that can be removed from a particular formula, while the derived formula has the same satisfiability ...
5
votes
1answer
172 views

Size of Formulas with no negative sign for Matrix Permanent

What is the best lower bound for algebraic formulas for Permanent of a matrix given that the formulas have no negative sign? Is there an exponential lower bound known for such formulas and what would ...
15
votes
0answers
324 views

Are there other proofs for Barrington's theorem?

I know that you can use other non-solvable groups, but is there a proof that uses a completely different approach? In case someone would not know the theorem: http://en.wikipedia.org/wiki/NC_(...
15
votes
1answer
397 views

Characterization of read-once formulae over the full binary basis

Background A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (...
18
votes
3answers
2k views

Shortest Equivalent CNF Formula

Let $F_1$ be a satisfiable CNF Formula with $n$ variables and $m$ clauses. Let $S_{F_1}$ be the solution space of $F_1$. Consider the problem of determining, given $F_1$, another CNF Formula $F_2$ ...
28
votes
4answers
787 views

Complexity of minimising polynomial formula size

Let $f(x_1,\dots,x_n)$ be a degree $d$ polynomial in $n$ variables over $\mathbb{F}_2$, where $d$ is constant (say 2 or 3). I would like to find the smallest formula for $f$, where "formula" and "...
25
votes
2answers
2k views

Formula size lower bounds for AC0 functions

Question: What is the best known formula size lower bound for an explicit function in AC0? Is there an explicit function with an $\Omega(n^2)$ lower bound? Background: Like most lower bounds, ...
10
votes
2answers
624 views

Shortest formula for an n-term monotone CNF

A monotone CNF formula with m terms on n variables ($x_1,\ldots,x_n$) is a formula of the form $f(x_1,\ldots,x_n) = \bigwedge C_i$, where each $C_i$ is an OR of some subset of the variables $x_1,\...
5
votes
2answers
375 views

Is the Balanced Boolean Formula problem solvable in sublogarithmic space if the input has a tree structure?

Suppose that instead of the usual linear work tape the input is given in a binary tree structure with n leaves and log n depth, the initial position being the root. At every node, we can step to its ...