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.

Filter by
Sorted by
Tagged with
6
votes
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'...
4
votes
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 ...
1
vote
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)$ ...
1
vote
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 ...
1
vote
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 ...
1
vote
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)...
1
vote
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 ...
0
votes
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 ...
2
votes
1answer
80 views

The complexity of expansion ratio (Cheeger constant) of a graph

Let $G=(V(G), E(G))$ be a graph on $n$ vertices and let $S$ be a subset of $V(G)$. The boundary of $S$, denoted by $\partial S$, is the set of edges $(i, j)$ such that $i \in S$ and $j \in V(G) \...
2
votes
0answers
48 views

Evidence Barvinok's or Lenstra's algorithm can be improved

Given a polyhedron $$Ax\geq b$$ there is an $n^{O(n)}poly(mL)$ time algorithm to count the number of integral points by Barvinok or identify an integral point by Lenstra where we assume $A\in\mathbb Q^...
1
vote
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 ...
3
votes
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 ...
4
votes
1answer
128 views

Finding a binary variable assignment to make a matrix with variables singular (over F_p)

Consider a square matrix defined over a finite field $M\in\mathbb{F}_p^{n\times n}$ having the following form $$M=\begin{bmatrix}a_{11}+b_{11}x_1&a_{12}+b_{12}x_1&\dots&a_{1n}+b_{1n}x_1\\...
0
votes
0answers
60 views

On complexity of a particular prime problem

Is the following problem in $PH$ and is it complete for any class? Problem: Is the $i$th bit of the $m$th prime $1$? It appears to require a counting quantifier which has to demonstrate witness is the ...
2
votes
0answers
29 views

Computing bipartite matching of size $k$?

Given a bipartite graph with $n$ vertices on each side and an integer $k$, how can we compute all bipartite matchings of size $k$? The problem of computing all perfect matchings is #P-complete. But I ...
1
vote
0answers
187 views

Solution to system of linear equations

Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
5
votes
3answers
420 views

Zero-knowledge proof for $P \ne NP$?

In computational complexity, $P \ne NP$ is a widely believed conjecture. Suppose that someone discovered a proof for it. He wants to publish a proof that he correctly proved the conjecture. I am aware ...
4
votes
0answers
144 views

Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

Crossposted at Theoretical Computer Science SE A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$....
1
vote
1answer
145 views

Complexity of a Diophantine equation having $\leq1$ solutions

We are provided a single Diophantine equation $$f(x_1,\dots,x_n)=0$$ having degree $\geq2$ and having the promise it has $\leq1$ solutions in the set $\{0,\dots,m-1\}^n$ and $t$ is the number of terms ...
10
votes
0answers
442 views

Inverse polynomial map $\mathbb{Z}^2\to\mathbb{Z}^2$ growing faster than $2^{2^n}$

Let $P, Q\in \mathbb{Z}[x, y]$ be polynomials with zero constant terms. Assume the induced map $\phi_{P, Q}:\mathbb{Z}^2\to\mathbb{Z}^2$ is injective. An example is $P=x+x^3 y^2, Q=y+x^2 y^3$. Can the ...
1
vote
0answers
91 views

Integrality of polyhedra

Given two polyhedra in $H$ representation $P_1:Ax\leq b$ and $P_2:Bx\leq c$ which are integral are bounded when is their intersection also integral? Given two polyhedra in $H$ representation $P_1:Ax\...
3
votes
0answers
100 views

Decidable equality for computable functions $\mathbb{N}\to\mathbb{N}$

Suppose we have two computable functions $f, g:\mathbb{N}\to\mathbb{N}$. When is $f=g$ algorithmically decidable? For example it is decidable if $f$ and $g$ are polynomials of a priori known degree.
14
votes
3answers
275 views

Exact coverability of $\mathbb{Z}_n$ by cyclic shifts of a given set — easy? NP-complete?

Recently Ernest Davis asked me about the following computational problem: we're given as input a composite integer $n$, a divisor $k$ of $n$, and a subset $S \subset \mathbb{Z}_n$ of size k. The ...
5
votes
0answers
80 views

Computing the zeta transform of a Boolean function: Space-time tradeoff

Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by $$\zeta_f(y) :...
0
votes
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....
0
votes
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 ...
1
vote
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 ...
0
votes
1answer
103 views

Complexity of solving linear equations plus disequality constraints $a \ne b$

Let $K$ be ring and $S$ linear homogeneous system with $n$ variables $x_i$ over $K$. Add to $K$ linear disequalities of the form $x_k \ne x_l$ and let the final system be $S'$. If $K=\mathbb{F}_2$, $...
1
vote
1answer
66 views

Algorithms for Polynomials Over a Real Algebraic Number Field, a reference

I need to find "Algorithms for Polynomials Over a Real Algebraic Number Field Ph.D. thesis, University of Wisconsin, Madison (1974) by Rubald". However I cannot find it online nor in my ...
1
vote
0answers
47 views

Complexity of checking if a set is an additive basis

A set of nonnegative integers $A$ is said to be an additive basis of order $k$ if every nonnegative integer is equal to the sum of $k$ elements of $A$. For example, Lagrange's theorem says that the ...
0
votes
0answers
17 views

Deciding unimodular versus a singular matrix

$L$ and $R$ are matrices in $\{0,1\}^{n\times n}$ given to you and one of $L$ and $R$ is singular and the other is unimodular on the identification as a biadjacency of a bipartite graph it has one ...
1
vote
0answers
46 views

$\mathsf{NP}$ complete version of Skolem arithmetic

Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities. ...
0
votes
0answers
19 views

Complexity of heaviest 2-optimal vertex-disjoint cycle covers

Calculating lightest vertex-disjoint cycle covers of finite complete symmetric graphs with weighted edges can be done efficiently and also renders the edge set of the calculated cycles free of pairs ...
0
votes
1answer
156 views

Algorithmically decide if an algorithm has optimal time complexity [closed]

Is there an algorithm with the following input and output? INPUT: an algorithm computing a function $\mathbb{N}\to\mathbb{N}$. The algorithm is guaranteed to halt on all inputs. OUTPUT: "YES"...
0
votes
1answer
62 views

What are the complexity classes of these problems about divisibility and coprimality?

The problems 'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?' 'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...
4
votes
0answers
193 views

What is the complexity class of this problem without Cramer's conjecture?

The problem 'Given $0<a<b$ is there a prime in the interval $[a,b]$?' is in $\mathsf{NP}$. If we assume Cramer's conjecture the problem is in $\mathsf{P}$ since if $b-a>(\log a)^{2+\epsilon}$ ...
0
votes
1answer
180 views

Maximize sum of edge weights on spanning tree

Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$. Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
1
vote
0answers
73 views

Complexity of polynomial inequalities

What is known about the complexity of deciding whether a finite set of polynomial inequalities in $n$ real variables with integer coefficients is satisfiable? Decidability is guaranteed by Tarski's ...
5
votes
0answers
143 views

Are there any neusis-hard/neusis-complete problems?

I have lately been enjoying Richeson's Tales of Impossibility (see MAA review), an accessible book on the famous problems of Euclidean geometry including angle trisection/cube doubling/heptagon ...
4
votes
1answer
149 views

Bi-Hölder embeddings of finite metric spaces

This is a reference request. There is a large body of work, I'm familiar with, that describes the existence of bi-Hölder embeddings of finite metric spaces into Euclidean space (such as this ...
3
votes
0answers
151 views

Games and the right mathematical framework for GANs

Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations. It is an important topic within deep learning. Are ...
0
votes
0answers
34 views

Hardness of generating Gaussian distribution

I would like to ask about the computational complexity of the problem of generating integers so that the obtained distribution is asymptotic to the Gaussian distribution. Any related reference is very ...
0
votes
0answers
55 views

Computing Partial Theta Series

Let $x\in [-1,1]$ and $\sigma \le 1$. For a certain application we need to compute $\sum_{j\ge 1}(-1)^{j-1}\exp\bigg(-\frac{j^2+2xj}{2\sigma^2}\bigg)$ to within an $\epsilon$-additive error. How fast ...
10
votes
1answer
616 views

What is known in general about the liquid transfer problem?

In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). ...
1
vote
0answers
80 views

what is the computational complexity of Louvain algorithm?

I am not able to find out the computational complexity of the Louvain Algorithm. Can anyone here help me? link of the paper given below: DOI: 10.1088/1742-5468/2008/10/P10008 https://doi.org/10.1038/...
3
votes
0answers
106 views

Creating an $n\times n$ grid with specified $2\times2$ sums [closed]

Suppose we have an $(n-1) \times (n-1)$ grid $A$ with numbers in each cell. How can we efficiently create a new $n \times n$ grid $B$ of digits where each $A_{i,j}$ is the sum of the corresponding $2\...
1
vote
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 ...
1
vote
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 ...
3
votes
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 (...
0
votes
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 ...

1
2 3 4 5
23