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,300
questions
2
votes
1
answer
44
views
Complexity for determining whether a given metric space is hyperconvex?
Suppose I am given a finite metric space as a distance matrix. What is the complexity of determining whether this metric space is hyperconvex?
Definition: A metric space is said to be hyperconvex if ...
6
votes
0
answers
103
views
Complexity of continued fraction arithmetic operations
Let $A = [a_0; a_1, \dots]$ and $B = [b_0; b_1, \dots]$ be continued fractions.
Let's say that we want to compute $A+B$ or $A \cdot B$ while staying in the continued fraction representation. So, for ...
- 1,141
2
votes
1
answer
118
views
The counterpart of productive set with polynomial computational complexity
For definition of productive set, see here and here, that is defined with computability, or computable function. Restricting computable function as function of polynomial computational complexity, is ...
- 3,000
3
votes
1
answer
777
views
Language equivalence between deterministic and non-deterministic counter net
One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that
cannot decrease below zero and cannot be explicitly tested for zero.
An OCN $A$ over alphabet $\sum$ accepts a ...
- 63
8
votes
1
answer
411
views
Classes of groups with polynomial time isomorphism problem
It is known that the isomorphism problem for finitely presented groups is in general undecidable. What are some classes of groups whose isomorphism problem is known to be solvable in polynomial time? (...
- 283
-3
votes
1
answer
518
views
Counter net decidability [closed]
Let one Deterministic Counter Net ($\mathrm{1DCN}$), which is a finite-state automata where every state is complete means all states has transition of all input symbols and their respective weight ...
- 63
5
votes
0
answers
157
views
Is the matrix multiplication exponent $\omega$ independent from the choice of the base field
The matrix multiplication exponent, usually denoted by $\omega_{F}$, is the smallest real number for which any two $n\times n$ matrices over a field $F$ can be multiplied together using ${\...
- 151
0
votes
0
answers
67
views
Complexity of vertex separator problem
Given a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$, a three-partition is a decomposition of $V$ into a triple $(V_1, S, V_2)$ such that vertices of $V_1$ are only incident to vertices ...
10
votes
1
answer
372
views
Can $N!$ be computed in less than $\mathcal{O}(N)$ operations?
The standard algorithm to compute the factorial function $N!$ via repeated multiplications has complexity $\mathcal{O}(N)$, in the model in which each operation costs 1, no matter how many digits the ...
- 756
1
vote
0
answers
30
views
Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector is in $NC$?
Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$
$$ax+by=c.$$
Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ ...
- 13.7k
1
vote
0
answers
101
views
On determinant and permanent of certain homotopy defined simple matrices
Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$
$$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$
hold ($per$ refers to permanent).
I. What ...
- 13.7k
1
vote
0
answers
161
views
On an optimization question
Suppose we have a square matrix $M=(1-z)A+zB$ where $A,B$ have integer entries from $\{0,1\}$ with $\det(A)+\det(B)=1$ and $\det(A),\det(B),per(A),per(B)\in\{0,1\}$ and we want to find $z\in[0,1]$ ...
- 13.7k
0
votes
0
answers
302
views
A question regarding an unprovability proof
Let LA denote polynomial time arithmetic, Con_LA the equation stating the
consistency of LA, LAJ the system LA+Con_LA, and E2A double exponential time
arithmetic.
A manuscript of mine provides a proof ...
- 131
0
votes
0
answers
136
views
Maximizing the norm of a sum of Hermitian matrices
Consider the following problem:
Problem: Given $n\times n$-Hermitian matrices $A_1,\dots,A_r$, find $e_1,\dots,e_r\in\{-1,1\}$ such that $\|e_1A_1+\dots+e_rA_r\|_\infty$ is maximized. Here the norm is ...
- 27.8k
1
vote
1
answer
166
views
Diagonally dominant matrix via rows permutation
Diagonally dominant matrices are required in many linear algebra algorithms such as the Gauss-Seidel algorithm.
Some matrices can be made diagonally dominant by permuting its rows and others cannot.
...
- 2,951
1
vote
0
answers
153
views
Fastest algorithm for finding the closest semi-definite matrix?
Given a real-valued, symmetric matrix $A \in \mathbb{R}^{n \times n}$, I'm interested in finding the closest positive semi-definite matrix $X^*\in \mathbb{R}^{n \times n}$:
$$
X^* = \mathop{\text{...
- 713
1
vote
0
answers
59
views
Is there any lower bound for basis computation in finite Abelian groups?
Victor Shoup in this paper has given a lower bound for discrete logarithm. The algorithms that I have come across use discrete logarithms (extended discrete logarithms) to compute a basis for a finite ...
- 11
1
vote
0
answers
53
views
Over a given finite field, how many couples of matrices there are, for which their minimal polynomials are co-prime?
Let ${\mathbb F}_{q}$ be a given finite field. How many couples of $n\times n$ matrices $\left(A,B\right)$ over ${\mathbb F}_{q}$, such that $\gcd\left(\mu_{A}\left(\lambda\right),\mu_{B}\left(\lambda\...
- 21
2
votes
0
answers
203
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...
- 13.7k
5
votes
0
answers
117
views
Finding an $\mathbb{F}_q$-point on one specific intersection of quadrics
Let $\mathbb{F}_q$ be a finite field of large characteristic and $a_1, a_2, \cdots, a_n \in \mathbb{F}_q$ be some pairwise different elements. I assume that $\sqrt{-1} \in \mathbb{F}_q$. Consider the ...
- 1,801
1
vote
1
answer
306
views
Is non-convex optimisation really in NP class?
Crossposted on Mathematics SE
I've seen in many optimisation papers the statement that general non-convex optimisation problem is NP-hard. If we assume that non-convex optimisation is in NP class, it ...
- 105
2
votes
0
answers
211
views
Pancake sorting problem – Is computing f(n) NP-hard?
The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems:
MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence ...
- 51
3
votes
1
answer
226
views
Complexity of inverting and multiplying against a symmetric Toeplitz matrix with two repeated entries
I know that the computational complexity of inverting a general $n \times n$ matrix $A$ is $O(n^{2.373})$ and multiplying it against an $n \times m$ matrix is $O(n^2m)$. Moreover, I've seen that ...
- 91
2
votes
2
answers
203
views
Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them cover all the nodes?
Given a directed graph $G=(V,A)$ and given for every pair of nodes $(i,j)$
a valid path $P(i,j)=(v_1=i,...,v_l=j)$ on $G$.
Find a minimum set of nodes $M$ such that $\bigcup_{(i,j)\in M\times M}P(i,j)=...
- 21
0
votes
0
answers
56
views
NC0 randomness vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
8
votes
0
answers
344
views
Worst-case complexity of calculating homotopy groups of spheres
Is the best known worst-case running time for calculating the homotopy groups of spheres $\pi_n(S^k)$ bounded by a finite tower of exponentials? How high is a tower? Does $O(2^{2^{2^{2^{n+k}}}})$ ...
- 827
3
votes
0
answers
64
views
Does this information theoretical thought experiment have a name or corresponding area of research?
I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
- 479
9
votes
2
answers
918
views
What theories are larger than the real closed field but still decidable?
It's well known that sentences about the real closed field can be decided by algorithm and the complexity of this is about $d^{2^{O(n)}}$ where $d$ is the product of the degrees of polynomials in the ...
- 2,283
5
votes
1
answer
449
views
Discrete log problem modified
Suppose one is given an odd prime $p$, a generator $g$ of $(\mathbb Z/p \mathbb Z)^*$ and two integers $a$ and $b$. Is there an efficient method to determine whether $\log_g a < \log_g b$? (Here we ...
- 2,539
0
votes
0
answers
117
views
Will an integer program to deterministically factor integers help derandomize $\mathbb F_q[x]$ factoring?
There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$.
Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in ...
- 13.7k
2
votes
1
answer
319
views
Modular square roots problem which is $NP$ hard
It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...
- 13.7k
9
votes
4
answers
2k
views
Computational complexity theoretic incompleteness: is that a thing?
Has anyone done research in an area that I have not heard of but that I want to call "Computational complexity theoretic incompleteness", which would mean not absolute incompleteness in the ...
- 193
3
votes
1
answer
377
views
What is the name for algebras generated by elements, all of whose cubes vanish?
Given a ring $R$ with identity $1$, we can define the exterior algebra of order $k$ over $R$ to be the algebra over $R$, generated by elements $x_1, \dots, x_k$ satisfying $x_i^2 = 0$ for each index $...
- 455
1
vote
0
answers
68
views
Is this factorization problem in EXP?
Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored.
However now consider integers of form $...
- 13.7k
1
vote
0
answers
43
views
Computational hardness of a discrete generalized rectangle packing problem
I have a decision problem that is clearly in NP, but I cannot seem to prove that it is in P, nor can I prove its NP-hardness. I attribute this more to my inexperience than to the problem's difficulty (...
9
votes
2
answers
2k
views
Why do almost all points in the unit interval have Kolmogorov complexity 1?
Re-posted from math.stackexchange as I did not get any answers there.
I am reading
Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, ...
- 297
3
votes
1
answer
312
views
How to find the maximum of a sum of squares of sums?
Is there any better than a brute force method for finding the maximum
$$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$...
user494931
5
votes
2
answers
246
views
Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?
It was shown in
P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short
vectors in a lattice
that the construction of a shortest nonzero vector of a Euclidean ...
- 435
2
votes
1
answer
199
views
Computational complexity and commuting functions, examples and conjectures
History of the question. I was proposing a conjecture here, called Prop. 1. Fedor Pakhomov showed a counter-example. Here I am proposing a slightly weaker version of the conjecture, Prop. 2, that ...
- 397
8
votes
1
answer
207
views
Computational complexity and commuting functions
EDIT: in this question, I was proposing a conjecture, Prop. 1. Fedor Pakhomov showed a counter-example. In this new question I propose a slightly weaker conjecture that holds even for that example and ...
- 397
13
votes
1
answer
561
views
Can we compute the first $n$ digits of $\pi$ in $F(n)$ time?
I've seen various fast algorithms for computing the first few, or directly the $n$-th, digits of $\pi$.
However, it seems to me that all these algorithms assume (see last sentence here) that there are ...
- 18.4k
1
vote
0
answers
117
views
Frog game on tree graphs is in NP but not in P (NP-complete)?
Problem
We can restrict ourselves to tree graphs. What is the complexity of the following problem?
Let $G$ be simple connected graph with vertices in $V$, edges in $E$, and a vertex weighted function $...
- 601
11
votes
1
answer
670
views
Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?
According to this source (p. 10), determining whether a simplicial complex is a simplicial sphere (the sphere recognition problem) is undecidable.
According to this source, determining whether a ...
- 12.6k
0
votes
0
answers
184
views
Future of complexity classes in case NP=P
The P=NP question is still unresolved and there is no hope that the situation will ever change.
Assume now the hypothetic situation that P=NP had been confirmed:
Questions:
what will become of the ...
- 12.7k
2
votes
0
answers
166
views
On GCD and lattice reduction
$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$.
Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector.
If $GCD$ is in $NC$ and in ...
- 13.7k
4
votes
0
answers
123
views
Lattice reduction of basis with non-integer coefficients
Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$.
I would like to perform lattice ...
- 554
1
vote
0
answers
106
views
Finding the optimal arithmetic circuit for evaluating a given polynomial
The Horner's algorithm takes as input a univariate polynomial $f(X)$ and an evaluation point $x$ and computes $f(x)$ using $O(\deg(f))$ field operations.
Suppose now that the polynomial $f(X)$ is ...
- 297
4
votes
0
answers
101
views
Questions in number theory related to $NC$ and $P$-completeness
Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$.
Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$.
Euclidean algorithm solves both.
My question is if either 1 or 2 is in ...
- 13.7k
1
vote
0
answers
69
views
What is the complexity of elgamal cryptosystem? [closed]
Its clear generation of keys based
On cyclic group and its generator for z_p
So my question
Does finding the generator efect on complexity
Moreove does the size of message M effect on the complexity?
- 11
2
votes
0
answers
186
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal simple polygons. Rapport showed that it is NP-complete to decide the existence of orthogonal simple polygon that passes ...
- 2,951