# Questions tagged [symmetry]

The tag has no usage guidance.

17 questions
Filter by
Sorted by
Tagged with
95 views

### Relationships between problem symmetry and its complexity

I read once that the more a problem has some symmetries the "easier" it is to solve and in particular its (time) complexity is polynomial. Conversely, when starting from a polynomial problem,...
224 views

### Is $GCT$ necessarily a negative result program?

$GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can ...
• 13k
2k views

### Computing the edge orbits of a graph (and discussing definitions)

A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a ...
1 vote
98 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 ...
• 311
83 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 ...
• 311
1 vote
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 $... • 1,572 9 votes 1 answer 204 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 ... • 1,572 14 votes 2 answers 747 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 ... • 1,572 0 votes 0 answers 51 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 ''... 1 vote 1 answer 368 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 ... • 119 6 votes 0 answers 279 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$... • 1,261 1 vote 0 answers 92 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$... • 1,292 4 votes 0 answers 141 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 ... • 13k 12 votes 1 answer 415 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, ... • 6,852 10 votes 2 answers 660 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 ... 6 votes 1 answer 539 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)$...