# Questions tagged [symmetry]

The tag has no usage guidance.

14 questions
38 views

### How to efficiently verify if a semantic symmetry of a CNF formula is valid?

It is easy to verify that a syntactic symmetry of a CNF formula is correct. Is it also possible to check in polynomial time that a semantic symmetry which is not a syntactic symmetry of a formula is ...
70 views

### Finding a largest symmetrical subset of a k-CNF propositional formula

I have a k-CNF propositional formula $F$ which do not admit any global symmetry i.e. there is no permutation $\sigma$ of its variables such that $\sigma(F) = F$ . I'm interested in finding the largest ...
If we have some string $x$ and a permutation $g$ which preserves the bits of $x$, we can store the value of $x$ on each of its $g$-orbits as well as $g$ instead of storing $x$ and we can reconstruct $... 1answer 145 views ### What is the probability that a random Boolean function has a trivial automorphism group? Given a Boolean function$f$, we have the automorphism group$Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$. Are there any known bounds on$Pr_f(Aut(f) \neq 1)$? Is there ... 2answers 676 views ### Are There Highly Symmetric NP- or P-complete Languages? Does there exist$L$, an NP- or P-complete language which has some family of symmetry groups$G_n$(or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on ... 0answers 38 views ### Number of common neighbors of any two adjacent vertices in a edge transitive graph is same or different? We have a theorem that, if the graph G is symmetric (both vertex and edge transitive) then G^p (by joining the vertices which are at the distance at most p in G) is also symmetric. See the reference ''... 1answer 213 views ### checking isomorphism between K regular graph Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that ... 0answers 266 views ### Is this graph polynomial known? Can it be efficiently computed? Consider a connected simple graph$G$with$n$vertices and$m$edges. View each edge$\ell$as a transposition$t_{\ell}$acting on the set of vertices. [To be more explicit, given an edge$\ell$... 0answers 86 views ### Restoring symmetry in certain combinatorial bijections? I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair$\cal{F} = (F,f)$where$F$is an$n$... 0answers 131 views ### Symmetry of optimal solutions to discrete optimization problems Given a graph, say one wants to find the clique number, independence number, chromatic number, vertex cover number etc., one knows that a solution exists. However if the solution space has more than ... 1answer 349 views ### Measuring the randomness of CNF formulas It's widely known that CNF formulas can be roughly partitioned in 2 broad classes: random vs. structured. Structured CNF formulas, in opposition to random CNF formulas, exhibit some sort of order, ... 2answers 606 views ### Approximating non-trivial graph automorphism? Graph automorphism is a permutation of graph nodes that induces a bijection on the edge set$E$. Formally, It is a permutation$f$of nodes such$(u,v)\in E$iff$(f(u),f(v))\in E$Define an ... 1answer 461 views ### The role of symmetry in geometric complexity theory? I'm not well versed in geometric complexity theory so my question could be trivial. I understand that GCT program studies the symmetries of determinant and permanent to prove Valiant's Hypothesis:$...
The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0. However, If $k(n)=O(\log n)$ ...