# 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,092
questions

**0**

votes

**1**answer

131 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"...

**3**

votes

**0**answers

118 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}$ ...

**8**

votes

**0**answers

113 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 ...

**0**

votes

**1**answer

54 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]$ ...

**27**

votes

**2**answers

933 views

### Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class.
Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...

**0**

votes

**1**answer

155 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

**0**answers

65 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

**0**answers

88 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 ...

**2**

votes

**2**answers

900 views

### Complexity of computing derivatives

Sorry if this is too simple. This is my first question here.
Suppose $f : R^n \to R$ is a differentiable function. Say that we can compute in $T$ arithmetic operations the value $f(x)$ at any point $...

**3**

votes

**1**answer

253 views

### What is the big-O time complexity of computing $1/N$ to $\log_{2}(N)$ bits of precision?

I am considering large integer values of $N$ (100 or more digits in base-$10$).
In my algorithm, I need to be able to compute the reciprocal of $N$ with enough precision that the repetend will have ...

**79**

votes

**25**answers

18k views

### Which popular games have been studied mathematically?

I'm planning out some research projects I could do with undergraduates, and it struck me that problems analyzing games might be appropriate. As an abstract homotopy theorist, I have no experience with ...

**4**

votes

**0**answers

127 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 ...

**11**

votes

**2**answers

374 views

### Techniques for proving relaxed one-wayness of functions

Existence of one-way functions is a widely accepted conjecture in complexity theory. A function is one-way if it is computable in polynomial-time but not invertible in polynomial-time (this is ...

**29**

votes

**2**answers

2k views

### Simulating Turing machines with {O,P}DEs.

Qiaochu Yuan in his answer to this question recalls a blog post (specifically, comment 16 therein) by Terry Tao:
For instance, one cannot hope to find an algorithm to determine the existence of ...

**0**

votes

**0**answers

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

**0**answers

54 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

**1**answer

577 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

**0**answers

28 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/...

**0**

votes

**2**answers

74 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 ...

**0**

votes

**1**answer

94 views

### Complexity of edge coloring graphs with $\Delta(G) \ge n/3$ assuming the overfull conjecture

Closely related to this on cstheory.
Let $G$ be graph of order $n$ with $\Delta(G) \ge n/3$.
Assume the overfull conjecture.
Can we edge color $G$ with minimal number of colors in polynomial time?
...

**3**

votes

**0**answers

104 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

**1**answer

86 views

### Is the graph minicut with the node cardinality constraint NP-hard?

I wonder whether the following problem is a well-studied NP-hard problem?
Get a graph $G$ and a number $k$, we partition the graph $G$ into two components where each component should have at most $k$ ...

**1**

vote

**0**answers

43 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 ...

**4**

votes

**0**answers

89 views

### Sub-quadratic Kolmogorov-Arnold?

The Kolmogorov-Arnold representation theorem says, essentially, that when computing a continuous function, the only multivariate function you really need is addition. (Somewhat) more precisely, it ...

**6**

votes

**2**answers

714 views

### Complexity of solving systems of linear diophantine equations

It is "well known" that a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$, $x\in \Bbb Z^n,b\in\Bbb Z^m$ for some $m,n \in \Bbb N$, can be solved in polynomial time, using Smith/Hermite Normal ...

**2**

votes

**0**answers

61 views

### Isomorphism preserving transformation graph to graph of logarithmic boolean width and bounded degeneracy

The paper On graph classes with logarithmic boolean-width
claims that some graph problems are fixed parameter tractable with parameter
the boolean width.
In particular, boolean-width of the complement ...

**6**

votes

**1**answer

612 views

### Complexity of counting words of given length in regular or context-free language

Let $L$ be a regular or context-free language over
alphabet $\{0,1\}$.
What is the complexity of counting words of length $n$ in $L$?
Is it possible to efficiently find if for given $n$
all words ...

**3**

votes

**1**answer

155 views

### Reference: Packing under translation is in NP

I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...

**1**

vote

**1**answer

104 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

**0**answers

88 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 (...

**4**

votes

**1**answer

224 views

### Polynomial size embeddings of toric varieties from polytopes?

Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan.
$X_P$ is always projective, because the collection of characters corresponding to the points $\...

**16**

votes

**2**answers

485 views

### Is this kind of “Gerrymandering” NP-complete?

[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.]
Consider the following simplified form of "Gerrymandering": You have $n^2$ ...

**1**

vote

**1**answer

83 views

### Exact volume calculation of a polytope is NP hard under which restrictions?

Computing the exact volume of a polytope given in half space representation seems to be NP-hard. One paper I found proved it is hard for rational coefficients. (However, the paper itself was behind a ...

**3**

votes

**0**answers

43 views

### Reference: Asymptotic bit-complexity of algebraic operations and transcendental functions

This question is a reference request. Does anyone know of a reference that lists the asymptotic bit-complexity of algebraic operations and transcendental functions implemented on a Turing machine that ...

**2**

votes

**0**answers

96 views

### Two from cubic subgraph hardness

The Problem
For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3.
The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...

**2**

votes

**1**answer

137 views

### On the computational complexity of Pepin's test

Let $F_{n} = 2^{2^{n}} + 1$, where $n > 0$.
Pepin's Test asserts that $F_{n}$ is prime if and only if $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.
QUESTION: What is the big-$\mathcal O$ complexity of ...

**14**

votes

**3**answers

1k views

### Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...

**2**

votes

**0**answers

21 views

### Algorithm for lightest unnested planar vertex-disjoint cycle-cover

Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the ...

**3**

votes

**0**answers

27 views

### Restriction of Rademacher Complexity

Let $F\subseteq C([0,1]^n,\mathbb{R})$ be a finite family of functions, which is non-empty. Let $A,B$ be subseteq of $[0,1]^n$, again non-empty, and let $Rad(C)$ denote the Rademacher complexity of ...

**3**

votes

**1**answer

394 views

### What's the runtime of this method and is this method correct?

Let $n=pq$ be the prime decomposition.
I am searching for $l$ such that there exists a $k$ with:
$$n^l = a \cdot 2^k + b$$
and
$$ 1 < \gcd(b,n^l) < n^l$$
Edit by comment of @GerryMyerson:
If $...

**3**

votes

**1**answer

462 views

### Is strictly harder than NP-hard cryptography possible?

Looks like there is cryptography based on NP-hard problem, e.g. McEliece cryptosystem. The algorithm is an asymmetric encryption algorithm and is based on the hardness of decoding a general linear ...

**2**

votes

**1**answer

830 views

### Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?

Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in ...

**1**

vote

**0**answers

55 views

### Polynomial time for a quadratic equation and linear inequalities?

Does anyone know how to find a feasible solution (or the infeasibility of any solution) in a polynomial time to the following problem:
\begin{align*}
xAx^t = 0, \\
Bx^t = c, \\
x_i \ge 0,
\end{align*}
...

**0**

votes

**0**answers

79 views

### What it is wrong with the proof $PH = AM = coAM$ based on FORMULA ISOMORPHISM?

Confusion is possible, but Emil's comment and a paper imply
major result: collapse of the polynomial hierarchy.
Q1 What is wrong with the proof that $PH = AM = coAM$ given below?
In a comment
about ...

**4**

votes

**0**answers

207 views

### Can we make cryptography signature algorithm based on hardness of isomorphism?

In public key cryptography, Alice knows functions $f$ and its inverse
$f^{-1}$. $f$ is public and $f^{-1}$ is secret. To sign a message
$m$, she gives $(m,a=f^{-1}(m))$. To verify a signature, the ...

**11**

votes

**3**answers

404 views

### Finite objects for which isomorphism is NP-hard or harder?

Are there finite objects for which deciding isomorphism
is NP-hard or harder?
Graphs and groups are not solutions.
Searching the web didn't return answer for me.
Partial result based on Chow's ...

**1**

vote

**2**answers

505 views

### Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...

**0**

votes

**0**answers

42 views

### Can you efficiently solve a linear system with a quadratic multivariate polynomial of degree 2?

Given a system of linear equations, $P=\{p_1,\dots,p_m-1\}$ and a $2$nd degree polynomial $p_m$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R},$ can you efficiently find a common zero of all of these ...

**4**

votes

**0**answers

171 views

### Does $\mathsf{Q}$ have any interesting provably recursive functions?

This question was asked and bountied at MSE without success.
For an appropriate theory $T$, say that an $n$-ary $T$-provably recursive function is a $\Sigma_1$ formula $\varphi$ with $n+1$ free ...

**4**

votes

**0**answers

146 views

### Disjoint paths in temporal graphs

Given a graph $G=(V,E)$ and a pair of source-destination nodes $s$ and $t$. Time is divided in periods with the total number of periods denoted by $T$. Each edge $e$ is either operational or broken at ...