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
1
vote
0answers
46 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
0answers
107 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
0answers
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
0answers
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
0answers
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
0answers
60 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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
123 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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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 $\...

1
2 3 4 5
22