# Questions tagged [computational-complexity]

This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.

1,121 questions
Filter by
Sorted by
Tagged with
0answers
104 views

### Certificate for computation of ideal class group

Is there a known way of producing a certificate that can be used to more quickly verify that an ideal class group of a number field was computed correctly? More formally, I would like to know if there'...
0answers
55 views

### Algorithms to factorize words into product of powers

I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references. Let $A$ be a finite set of symbols, are there ...
0answers
53 views

### Subgraph isomorphism problem with linear map

I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem: Problem 1: Given two graphs $G=(V, E)$ ...
0answers
17 views

### Reporting uncoverable directed simple cycles in digraphs

What is known about cycles in digraphs that can't be member of any of that digraph's vertex disjoint directed cycle covers as illustrated below? in that "cat's eye graph" the green cycle ...
1answer
226 views

### Could somebody suggest a way to determine if a parallelogram contains another parallelogram?

I thought of one way to do this. Using the algorithm which determines if a point is inside a parallelogram, one can determine if the polygon contains the point within $2N$ steps ($N=2$ for ...
0answers
31 views

### Computational complexity of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...
0answers
84 views

### Promise version of minimum distance

It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard. This immediately also says that given a code $C$, calculating minimum hamming ...
0answers
60 views

### Time complexity of asymmetric sums of divisor function

Let $\sigma_0:\mathbb{Z}_{\geq 1}\to \mathbb{Z}_{\geq 1}$ be the divisor counting function. Naively it seems the time complexity of computing $\sum_{i=1}^n \sigma_0(i)$ is at least linear but it can ...
1answer
80 views

0answers
62 views

### Counting $\bmod 2$ number of vertices of sparsely represented polyhedra

Given a polyhedron $$Ax\geq b$$ is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$? Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
0answers
43 views

### Modular counting of integral points under sparse non-negativity

Given a polyhedron $$Ax\geq b$$ where every entry of $A,b$ are non-negative and $A\in\{0,1\}^{m\times n}$ and there are $O(1)$ (say $\leq8$) non-negative entries per row of $A$ is it possible to ...
1answer
128 views

0answers
53 views

### Primality of $n$ bit integers in depth $n^\alpha$ under standard conjectures?

Denote $\mathsf{NC}(\mathsf{SUBLINDEPTH}(n),f(n))$ to be set of boolean circuits of fan-in $2$ which can be represented by depth $\cap_{\alpha>0}\mathsf{}n^\alpha$ and $f(n)$ sized Boolean circuits....
1answer
106 views

### What is the computational complexity of the calculation of $\Psi(x)$?

What is the computational complexity of the calculation of $\Psi(x)$ described below: Let $\left\{ f_i : \{0,1,\dots,m\} \to \mathbb{R} \right\}_{i=1}^n$. For each $x \in \{0,1,\dots,m\}$ we ...
0answers
60 views

### What is the computational complexity of solving a highly underdetermined system?

Let $F$ be a finite field with $q$ elements. Consider an underdetermined system of linear equations with $m$ equations and $n$ variables where $n\gg m$. What is the complexity of solving such a highly ...
1answer
103 views

0answers
55 views

### Reduction graph isomorphism to maximum independent set in very dense graph

We got a reduction graph isomorphism to MIS in a very dense graph, or alternatively negative monotone 2-CNF to MAX-ONEs with a formula with many clauses. Let $G,H$ be graphs of order $n$ and adjacency ...
1answer
110 views

### Complexity of solving $\sum_i A_i X B_i = C$

Is anything known about computational complexity of finding $X$ which satisfies the following matrix equation? $$\sum_i^n A_i X B_i = C$$ With $A_i,B_i,C$ dense $d\times d$ matrices. Any literature ...
0answers
94 views

### Can equality of chromatic symmetric functions of two trees be checked in polynomial time?

Stanley defined chromatic symmetric functions (CSF) in 1995 (Advances in Math) where he conjectured that trees can be distinguished by their CSF. However, tree isomorphism is decidable in P (...
2answers
83 views

### Optimal path with multiple costs

Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. Given vertices $s$ and ...