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

**1**

vote

**0**answers

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

**-3**

votes

**0**answers

109 views

### Integration modulo integers

$f(x,\theta)=\frac{g(x,\theta)}{h(x,\theta)}$ be a function parametrized by $x\in\mathbb N$ such that its integral with $\theta\in[a,b]$ for fixed $a,b\in\mathbb R$ is always an integer.
The ...

**0**

votes

**0**answers

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

**1**

vote

**0**answers

67 views

### Computational complexity in linear solvers

I have recently been trying out methods of coding for solving systems of linear equations on Python. Of course, I first used the inbuilt function $\mathit{inv}$ under certain if-conditions to obtain ...

**0**

votes

**0**answers

38 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

61 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

85 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

91 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

86 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

69 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

74 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

112 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

60 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

41 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

136 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

49 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

67 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

892 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

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

**0**

votes

**0**answers

40 views

### Complexity of pseudo-inverse of random matrix

Assume that $\mathbf{A}_{M\times N}$ is a sparse complex matrix. Then, what is the complexity of computation of its pseudo inverse, i.e.,
$$\mathbf{A}^{\mathrm{H}}(\mathbf{A}\mathbf{A}^{\mathrm{H}})^{-...

**3**

votes

**0**answers

145 views

### The complexity of cutting hackers in a computer network

Let $l_1,l_2,\dots,l_m$ be parallel lines in the plane, say $l_k=\mathbb R\times\{k\}$. On the $k$th line fix a set $V_k$ consisting of $n_k$ points.
Let $(V,E)$ be a directed graph whose set of ...

**0**

votes

**2**answers

185 views

### Limited sum for whole sum approximation

Let $d_n, n\in\{1,2,\cdots,N\}$ be $N$ realizations drawn independent and identically from uniform distribution on $(0,L)$ where $L=\gamma\sqrt{N}$ with constant $\gamma$. Suppose that we need to ...

**5**

votes

**0**answers

52 views

### special classes of ideals (eg. toric) that admit faster Buchberger algorithm?

I have heard that toric ideals allow one to speed up the Buchberger algorithm considerably (see Grobner bases of toric ideals, Remark 2,3). My question is two-fold:
What are the precise complexity-...

**1**

vote

**1**answer

77 views

### Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

Let $G$ be connected simple graph.
Clique cover of graph $G$ is partition of the vertices of $G$
into $k$ disjoint cliques $D'_i$.
Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle
in ...

**1**

vote

**1**answer

124 views

### Category of finite models of a $\tau$-sentence

Let $\varphi$ be an $\tau$-sentence, we define the generalized spectrum of $\varphi$ as the class of its finite models, $$\text{GenSpec}(\varphi):=\{\mathcal{A}; \mathcal{A} \models \varphi, \lvert A\...

**5**

votes

**0**answers

253 views

### The expressiveness of functions computable on trees

Motivation:
Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...

**1**

vote

**0**answers

25 views

### Computational complexity of higher order orthogonal iteration for Tucker decompositions

I am currently doing background reading for my Masters Thesis. I am working with tensor decompositions, where by tensor I simply mean a multi-dimensional array. The aim of my masters project is to ...

**1**

vote

**0**answers

90 views

### Does relationship between c.e.set, productive set, immune set, ML-random set exist between sets of class of other level

Is relationship between c.e.set, productive set, immune set, ML-random set similar to relationship between polynomial complexity set, polynomial complexity-productive set, P-immune set, P-random set?

**1**

vote

**1**answer

124 views

### Gröbner basis via integer programming

I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating ...

**0**

votes

**1**answer

100 views

### Are all $P$-noncomputable sets $P$-random? [duplicate]

$P$ means polynomial complexity.
$S_p$ is class of all $P$_random sets, and $S_{pc}$ is class of all $P$ incomputable sets, is $S_{pc} \setminus S_p$ empty? If not empty, any example?
what is the ...

**3**

votes

**1**answer

239 views

### Relationship between P-noncomputable and P-random sets

$P$ means polynomial complexity.
$S_p$ is the class of all $P$_random set, and $S_{pc}$ is the class of all $P$ incomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example?
what is ...

**2**

votes

**0**answers

85 views

### Time complexity of randomized algorithm: right-multiplying by random elements $z_i$ from a group $H$ to achieve $H$-invariance

Note: This question was inspired by a related question about the Quantum Merlin Arthur (QMA) complexity class on Quantum Computing Stack Exchange. I was deliberating whether to ask this on CS Theory ...

**1**

vote

**0**answers

37 views

### Compute irreducibles of monoid

Given $n > 0$ and $w \in \mathbb{Z}^n$. Is there an efficient algorithm to compute the set of irreducible elements of the monoid $M_w = \{x \in \mathbb{N}^n \mid \langle x,w\rangle = 0 \}$?
Here, ...

**2**

votes

**1**answer

119 views

### Intersection of a $\mathbb{Q}$-affine space with $\mathbb{Z}^n$

Let $E$, a $\mathbb{Q}$-affine space of arbitrary dimension included in $\mathbb{Q}^n$. Is it possible to check efficiently if $E \cap \mathbb{Z}^n$ is empty or not?
If is an hard problem could give ...

**2**

votes

**1**answer

88 views

### Can quantum codes have more than $c \cdot \sqrt{N}$ correction distance for N encoding qbits?

I'm not an expert in quantum computing at all, but recently I've started to learn it (read Shen-Vyalyi-Kitaev's book and looked up some other literature here and there).
There are few remarkable ...

**0**

votes

**0**answers

11 views

### Complexity of MIS for threshold hypergraphs

Given integer positive weights $w_i$ for $[n] = \{1,\dots,n\}$ and threshold $t$, consider ALL subsets of $[n]$ of weight exactly $t$. They form a hypergraph.
What is the complexity of maximum ...

**0**

votes

**1**answer

63 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?
...

**2**

votes

**0**answers

50 views

### A combinatorial question about encoding the subsets of logarithmic-bounded cardinality

Let $k \in \mathbb N - \{0\}$ and $f(n) = \binom n 0 + \binom n 1 + \dotsc + \binom n {\log^k n}$.
Our question is:
$f(n) = o(2^{\log^{k+1} \ (n)})$ or $f(n) = \Theta(2^{\log^{k+1} \ (n)})$, which ...

**1**

vote

**1**answer

51 views

### Complexity classes generated by differential equations

The quantum computer can be represented as a turing machine that sets up initial conditions for Schrodinger-like equation plus a fast ($O(1)$) solver for that equation.
Is there a general study for ...

**0**

votes

**0**answers

62 views

### A variant of weighted set cover problem

I came across a paper that proves a generalized version of the weighted set cover problem is NP-complete.
The problem is stated as follows: Given a collection of $n$ elements, a collection of ...

**3**

votes

**1**answer

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

**3**

votes

**1**answer

124 views

### How does the complexity of calculating the Permanent imply the NP completeness of directed 3-cycle cover?

In their paper Two Approximation Algorithms for 3-Cycle Covers of Markus Bläser and Bodo Manthey it is stated that:
"...deciding whether an unweighted directed graph has a 3-cycle cover is already NP-...

**1**

vote

**0**answers

42 views

### Coloration of an interval graph with constraints [closed]

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...

**0**

votes

**0**answers

37 views

### Algorithmic complexity of deciding the existence of regular $\mathrm{f}$-factors in graphs

Finding regular $\mathrm{f}$-factors in undirected simple graphs can be reduced to finding a perfect matching by utilizing the gadgets of Tutte or of Lovász and Plummer; there are several algorithms ...

**-1**

votes

**1**answer

215 views

### how do you convert binary to decimal [closed]

Suppose I have computed $\pi$ to 4 trillion binary digits
(1 trillion hex digits). I want to convert to decimal. You could remove the leading $11_2=3_{10}$ and then multiply the remaining number by $...

**5**

votes

**0**answers

93 views

### Is integer circuit membership undecidable?

According to wikipedia
integer circuit
in its simplest form is succinct representation of multivariate polynomial with
integer coefficients. Decidability if an integer is represented by the integer ...

**0**

votes

**1**answer

145 views

### Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]

Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...

**1**

vote

**0**answers

75 views

### Deciding if a set of hyperplanes passes through a point

There is a set of vectors $\vec a_{k,i}$ with $k\in\{1,\dots,n\}$ and $i\in\{0,1\}$,
such that every $n+1$-tuple $\{\vec v_{1,s_1},\dots,\vec v_{n,s_n},\vec v_{r,1-s_r}\}$
is linearly independent for ...

**4**

votes

**1**answer

171 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 $\...