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

**1**

vote

**1**answer

97 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

62 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

**2**answers

68 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**

vote

**1**answer

78 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

42 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

91 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

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

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

**3**

votes

**1**answer

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

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

**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

167 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

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

**11**

votes

**1**answer

700 views

### How did the Baker-Gill-Solovay paper come to be?

How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...

**2**

votes

**0**answers

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

**4**

votes

**1**answer

178 views

### NP-hardness of a sequence problem

Given $n$ binary sequences $s_i$ ($1\le i\le n$) with common period $T$. Let $s_i^{t_i}$ denote the sequence obtained by cyclically shifting $s_i$ for $t_i$ bits. The $n$ sequences form a good system ...

**1**

vote

**0**answers

36 views

### Meaning of L-reduction from Dominating set problem

We are working in a variation of Locating dominating sets. Recently, we realized that the reduction from dominating set to our problem in proving its NP-completeness turns out to be also an L-...

**1**

vote

**0**answers

121 views

### Checking existence of proofs of fixed length

This question is a continuation of a related previous question (check here).
Let $\mathcal{L}$ be a recursive first-order theory with the Hilbert-Ackerman's proof calculus, and such that the ...

**4**

votes

**1**answer

183 views

### Computational complexity of proof verification

Let $\mathcal{L}$ be a recursive first-order theory, with a deductive system $\Xi$ (for instance, Hilbert-Ackerman proof system). Let $\phi$ be a formula and let $l=(\psi_1, \ldots, \psi_n=\phi)$ be a ...

**0**

votes

**0**answers

126 views

### Counting points in elliptic curves

Given an elliptic curve over $\mathbb Z_n$
Is it $\#P$ hard to compute $\# E(\mathbb Z_n)$?
Is it $PP$-hard to compute $\# E(\mathbb Z_n)\leq\frac n2$?
Is it $\oplus P$ hard to compute $\# E(\...

**1**

vote

**0**answers

55 views

### The chromatic polynomial of a line graph

Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph?
There already exist characterizations of line graph ...

**0**

votes

**0**answers

36 views

### Is there a reversible fully polynomial-time approximation scheme for polygonal billiards?

Let $P \subset \mathbb{R}^2$ be a polygon with rational coordinates, and consider discrete billiards inside $P$, where a ball (of zero radius) moves by steps of fixed length on each step, in a ...

**6**

votes

**0**answers

113 views

### The provability logic of $I\Delta_0+\Omega_1 $ and complexity theory

Almost 30 years ago, a number of folks in provability logic tried to show that GL (see for instance the excellent survey by Rineke Verbrugge here) is indeed the logic of $I\Delta_0+\Omega_1$ (in the ...

**0**

votes

**1**answer

97 views

### Linear programming with exponential inequalities and rational variables

If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...

**0**

votes

**0**answers

15 views

### Complexity of finding matchings with bounds on weight-sum

Question:
what is the complexity of finding a matching of maximal weight-sum below a given bound?
I couldn't find anything in that respect online; maybe only because I do not know what to feed into ...

**12**

votes

**0**answers

189 views

### Does the Angel have to be really smart?

My question is about the computational complexity of the Angel's strategy in the Angels and Devils game, tl;dr does the Angel have a polynomial time strategy.
I'm a big Conway fan, so as you can ...

**0**

votes

**1**answer

71 views

### Complexity of edge coloring of class 1 graphs

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it ...

**1**

vote

**0**answers

26 views

### Modified straightline complexity of almost square of sums

Assume every linear operation (such as inner product with constant vector) can be performed in one step and multiplication by variables (quadratic operation) can be performed in one step.
We know the ...

**2**

votes

**0**answers

53 views

### Number of solutions to linear diophantine equations, with natural coefficients in a box

Let c, k, d $ \in \mathbb{N} $, let a, x $ \in \mathbb{N}^k $ suppose for all i $ \leq $ k, $ x_i \leq d $, $ a_i \in \mathcal{O}(d2^i) $ and $ \sum{a_ix_i} = c $ my question is for the value of c ...

**0**

votes

**0**answers

35 views

### A quasi-polynomial time PTAS for a MAX SNP-hard problem implies that $NP \subseteq QP$

I'm reading a paper [Jiang, Tao; Li, Ming;
On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput. 24 (1995), no. 5, 1122–1139.] with some non-...

**0**

votes

**0**answers

43 views

### Gröbner basis and integer programming

I was studying about grobner basis and observed one application of it in integer programming which is pretty much amazing but tougher than available methods like branch bound. Then what is the benefit ...

**1**

vote

**0**answers

130 views

### Computational complexity of computing the trace of a matrix product under some structure

I have two problems related to computing some trace, and some (possibly suboptimal) answers. My question is about a potential more efficient algorithm for each one. (More interested in an answer to ...

**2**

votes

**1**answer

112 views

### Complexity of set-partition problems

given a universe $\mathcal{U}$ of elements and a system $\mathcal{S}$ of weighted subsets of $\mathcal{U}$ whose union covers $\mathcal{U}$.
Assuming the existence of at least one subsytem $S\...

**2**

votes

**0**answers

108 views

### Double Diophantine approximation

Let $0 < \alpha < 1$. For any $n$ there is a closest lower Diophantine approximation $\max p / q \leq \alpha$ with integer $0 \leq p < q \leq n$. It can be found efficiently, e.g., with Stern-...

**1**

vote

**2**answers

89 views

### One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets

Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.
Now, is it possible to color vertices in $U$ with 3 colors ...

**3**

votes

**1**answer

72 views

### What is known about computing all binary error correcting codes of given parameters?

Define a binary $(n, M, 2e + 1)$ code to be a code $C$ having $M$ code words in $\mathbb{F}_2^n$ whose minimum distance is $2e + 1$.
Are there any sources about using algorithms to find all given ...

**1**

vote

**1**answer

85 views

### Low-complexity method for sub-matrix inversion

Assume that $\mathbf{A}$ be an $N\times N$ matrix. We know that the complexity of the computation of matrix inversion is $\mathcal{O}(N^3)$. Let define $\mathbf{D}=\mathbf{A}^{-1}$. Now, assume that $\...

**0**

votes

**0**answers

114 views

### How can GL(n) acts on the determinant polynomial?

I'm reading Landsberg's paper, which provide an introduction to geometric complexity theory. At chapter 2 of this paper, the author defined the following objects:
Let $W = \mathbb {C}^{n^2}$, $det_n \...

**4**

votes

**0**answers

63 views

### Amortized complexity of P

Let $P$ be the class of all polynomial time computable functions from $\{0,1\}^*\rightarrow \{0,1\}$. For any $f\in P$, define function $f^A:\mathbb{N}\rightarrow \{0,1\}^*$ by
$$f^A(n)=(f(x_1),\cdots,...

**0**

votes

**0**answers

47 views

### Reference about Relation between Probabilistic Turing Machine and Turing Machine of every hierarchy

What are the relation between Probabilistic Turing Machine and Turing Machine of every hierarchy, for instance, are the Probabilistic PDA and NPDA equivalent? the Probabilistic LBA and LBA equivalent?...

**2**

votes

**0**answers

147 views

### Decoding Fock spaces

Technically, the Fock space is (the Hilbert space completion of) the direct sum of the symmetric or antisymmetric tensors in the tensor powers of a single-particle Hilbert space H.(Wikipedia)
...

**0**

votes

**0**answers

55 views

### Complexity of transforming a polynomial to its canonical form

Why transforming the polynomial $F(x)=\Pi_{i=1}^{d}{(x-a_i)}$ to its canonical form (@) requires $\theta(d^2)$ multiplications of coefficients?
(@) The canonical form is defined as $\Sigma_{i=0}^{d}{...

**0**

votes

**0**answers

22 views

### Complexity of combined trajectory compression algorithm

Is it possible to calculate the complexity of the combined algorithms (TD-TR-SP, TD-SP-TR) provided here:
A new perspective on trajectory compression techniques
In more details, TD-TR-SP algorithm ...

**1**

vote

**1**answer

77 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$ ...

**20**

votes

**0**answers

921 views

### Do we know how to determine the $2^{2020}$ decimal of $\sqrt{2}$?

In the case of $\dfrac{1}{7^{800}}$ it's easy, to find the $2^{2020}$ decimal, but what about the simplest of the irrational numbers.
Question: Do we know how to determine the $2^{2020}$ decimal of ...

**2**

votes

**0**answers

385 views

### A decision problem from sheaf set theory?

Let $V^{X}$ be a sheaf model of ZF set theory, where $X$ is a topological space as it is defined in [1].
Let $T(y_1,\ldots,y_n)$ be an $B(T)$-free algebra as it is defined in [2], where $B(T)$ is the ...