Skip to main content

Questions tagged [symmetry]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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,...
deb2014's user avatar
4 votes
1 answer
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 ...
Turbo's user avatar
  • 13k
10 votes
2 answers
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 ...
Arnaud Casteigts's user avatar
1 vote
0 answers
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 ...
RTK's user avatar
  • 311
4 votes
0 answers
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 ...
RTK's user avatar
  • 311
1 vote
1 answer
97 views

What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?

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 $...
Samuel Schlesinger's user avatar
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 ...
Samuel Schlesinger's user avatar
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 ...
Samuel Schlesinger's user avatar
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 ''...
user62619's user avatar
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 ...
v78's user avatar
  • 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$ ...
user3483902's user avatar
  • 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$...
NisaiVloot's user avatar
  • 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 ...
Turbo's user avatar
  • 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, ...
Giorgio Camerani's user avatar
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 ...
Mohammad Al-Turkistany's user avatar
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: $...
Mohammad Al-Turkistany's user avatar
23 votes
2 answers
1k views

Relationship between symmetry and computational intractability?

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)$...
Mohammad Al-Turkistany's user avatar