# All Questions

14 views

### Strategy for connecting 2 points without intersecting previously drawn lines

I have to connect two given points with a line. Then again two new points are selected and these have to be connected as well however without intersecting previously drawn lines and so on for any ...
59 views

### Time Complexity and Optimization for the Algorithm?

I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity. The algorithm is as follows : Label all the vertices ...
50 views

### Claims on bridges between disjoint subgraphs of a graph

I have a directed graph $G = (V, E)$ where there are several disjoint subgraphs, $G_i$. I do not wish to make any claims about the connectivity within each of these. I nominate two sets of verticies ...
41 views

### Fourier transformation of the automorphism group of a graph

Following is an example of permutation cycle graph $\Gamma$ for a given permutation $\pi = \left(1\text{ } 2\right) \left(3\text{ } 4\text{ } 5\text{ } 6\right)$. The adjacency matrix $A$ is given ...
25 views

### Factoring random selfreducibility analogy from discrete logarithm

It is stated in https://en.wikipedia.org/wiki/Random_self-reducibility#Discrete_logarithm that if discrete log is easy for $\frac 1{poly(\log|G|)}$ of all inputs, then discrete log has a randomized ...
85 views

### Theoretical computer science self-study resources for programmers

I am a pretty proficient software engineer, but I don't know much theory. I want to learn more theory. Particular topics that I am interested in are: computational complexity, formal languages, and ...
83 views

124 views

### Tree decomposition for DAGs

Tree decompositions and treewidth are a standard way to measure how close an undirected graph is to a tree. I am studying decompositions of directed acyclic graphs (DAGs), and have come to define them ...
132 views

### Is this problem #P-hard and why?

Problem: In a directed graph $G=(V,E)$, each edge $e\in E$ is associated with a weight $w_e$ which is geometrically distributed with a parameter $p$, i.e. $P(w_e=i)=p(1-p)^{i-1}, i\geq 1$. $s,t$ ...
97 views

### Complexity class for some group and graph homomorphism problems

Given two groups $G_1$ and $G_2$ what is the complexity class in which the following problem belongs? $$\mathsf{Is }|Hom(G_1,G_2)|>0$$ Given two graphs $H_1$ and $H_2$ what is the complexity ...
86 views

### An algorithm that determines if regular language accepts all string of its alphabet [closed]

Let $L$ be a regular language with the alphabet $\Sigma$. I'm trying to find an algorithm to tell whether $L=\Sigma^{*}$, whether $L$ accepts all strings in its alphabet. I think this algorithm uses ...
80 views

### Some nuances on Group and Subgroup Isomorphism?

(1) Is it known Group Isomorphism is in $\mathsf{coNP}$ and is the conjecture so? Is there a good reference for $\mathsf{coNP}$-ness in similar situations? (2) Is subgroup isomorphism ...
(1) Is there a relation ( conjectured relation) between $\mathsf{\#P}$ and $\mathsf{CH}$? (2) How does $\tau$ conjecture in complexity of factorial fit in the picture? Is there a good reference? ...
Let $U$ be a small finite set. Consider the following problem: Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$. Output: a (contiguous) substring of $v$ of length $k$ with the minimum ...