# 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,262 questions
Filter by
Sorted by
Tagged with
0 votes
0 answers
11 views

### Convergence bound for zero-order optimization method

I would like to understand the error bound for a particular zero-order optimization method: (stochastic) difference method. To solve an nonsmooth optimization problem $min_x G(x)$ where $G$ is only a ...
• 759
3 votes
1 answer
195 views

### MIP*=RE theorem and its impact on logic and proof theory

In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
• 9,038
1 vote
0 answers
37 views

### Hardness of an optimization problem when some variables are fixed

Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed. With the two (related) examples, it is clear that ...
1 vote
0 answers
33 views

### Are the lower elementary functions closed under limited recursion?

The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and ...
• 1,223
0 votes
0 answers
75 views

• 9,038
2 votes
1 answer
105 views

### Optimization over permutation

The Problem This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
• 43
1 vote
0 answers
82 views

### Computing sine of gamma function

In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step? Is there a ...
2 votes
1 answer
50 views

### Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?

According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard. However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
• 123
0 votes
0 answers
19 views

### Are there any known lower complexity bounds on solving positive semidefinite or positive semidefinite feasibility problems?

I've been trying to attack the problem posted here, about quickly checking if a matrix has any positive semidefinite completions. I suspect that the answer to the question is "no", because ...
• 101
0 votes
0 answers
46 views

### On diagonalizations over complexity classes

I am looking for the following PhD thesis, but could not find it, and all my attempts for finding it failed. I am wondering if there is a way to get it: On diagonalizations over complexity classes By: ...
• 31.2k
2 votes
1 answer
39 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
58 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 ...
2 votes
1 answer
110 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 ...
• 2,848
3 votes
1 answer
710 views

### 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 ...
• 73
8 votes
1 answer
356 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? (...
• 273
-3 votes
1 answer
510 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 ...
• 73
5 votes
0 answers
86 views

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 ${\... 0 votes 0 answers 44 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 317 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 ... • 746 1 vote 0 answers 28 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.5k 1 vote 0 answers 99 views ### On determinant and permanent of certain homotopy defined simple matrices Let$A_1,A_2,B_1,B_2$be four$n\times n0/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.5k 1 vote 0 answers 155 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.5k 0 votes 0 answers 299 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 122 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 ... • 26.8k 1 vote 1 answer 142 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. ... 1 vote 0 answers 67 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{... 1 vote 0 answers 54 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 52 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\... 2 votes 0 answers 192 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.5k 5 votes 0 answers 111 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,739 1 vote 1 answer 196 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 ... 0 votes 0 answers 27 views ### Complexity of a specific constrained maximum weight matching Let G(V,E)=K_n be a complete symmetric and edge-weighted graph with n vertices and let H be a Hamilton cycle in G, i.e. a connected 2-factor. Question: what is the complexity of calculating ... • 12.3k 2 votes 0 answers 167 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 ... 3 votes 1 answer 137 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 ... • 71 2 votes 2 answers 174 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)=... 0 votes 0 answers 55 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 326 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}}}}) ... • 595 3 votes 0 answers 61 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 898 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 ... • 1,968 5 votes 1 answer 418 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,451 0 votes 0 answers 113 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.5k 2 votes 1 answer 210 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.5k 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 365 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 ... • 397 1 vote 0 answers 62 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.5k 1 vote 0 answers 34 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, ... • 251 3 votes 1 answer 265 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}$$... 5 votes 2 answers 217 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 ...
• 425