computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; ...

learn more… | top users | synonyms (1)

5
votes
1answer
2k views

What is the time complexity of truncated SVD

Full SVD, on an m*n matrix $A$, $[U,S,V] = svd(A)$, would cost $O(m^2n + mn^2 + n^3)$ time. But what is the time complexity if we only need the $k$ largest singular values, say, $[U_k,S_k,V_k] = ...
9
votes
2answers
234 views

Finite objects for which isomorphism is NP-hard or harder?

Are there finite objects for which deciding isomorphism is NP-hard or harder? Graphs and groups are not solutions. Searching the web didn't return answer for me. Partial result based on Chow's ...
7
votes
0answers
100 views

Is there an efficient algorithm for testing isomorphism of projective planes?

Isomorphism testing is a core problem in computational complexity. Recently, Babai has shown that Graph Isomorphism problem for general graphs can be solved in quasipolynomial time. Long time before ...
5
votes
1answer
79 views

Complexity of integer programming with added predicates

A classical theorem in Integer Programming by Lenstra says that any integer system $$A x \le b$$ can be solved in polynomial time, where $A \in \mathbb{Z}^{m \times n}, x \in \mathbb{Z}^n, b \in ...
39
votes
3answers
8k views

Testing whether an integer is the sum of two squares

Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer $n$ is a sum of two squares? By "fast" here I mean polynomial time (i.e. time $O((log n)^{O(1)})$). Note ...
2
votes
0answers
157 views

Complexity of an algorithm to solve linear diophantine equations

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here. I want to know the optimal complexity of an algorithm (I mean the ...
1
vote
1answer
81 views

Complexity of $\mathsf{gcd}(a,b)\bmod N$

Given $a,b\in\Bbb N$ where each $a,b$ is $n$-bits, we can compute $\mathsf{gcd}(a,b)$ in $cn^{1+\epsilon}$ bit operations for some fixed $c\geq1$. My query is given $N,a,b$ where $a,b$ is $n$-bits ...
0
votes
0answers
42 views

Analogues of Specker sequences for different complexity classes

Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i ...
1
vote
0answers
55 views

bounded degree graph colouring.

I was wondering if anyone could provide references on the following: Is determining the chromatic number of a bounded degree graph APX-complete? 2.I've seen the result that states it is NP-hard ...
2
votes
0answers
45 views

Hypergraph edge colouring

I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...
19
votes
3answers
1k views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...
-2
votes
1answer
117 views

Turing and Many one reductions in computability versus complexity

What are some non-trivial (please exclude poly time definitional difference) differences between Turing versus Many-one reductions in computability theory and those that occur in complexity theory?
7
votes
2answers
707 views

Complexity of Turing Machine behavior

If one looks at the code for a Turing Machine (TM) with $q$ states and, let's say, $2$ symbols, they all look pretty much the same: A list of $5$-tuples: $$ < state, symbol{-}read, ...
1
vote
0answers
63 views

Calculation of cardinality of Jacobians

The problem of calculation the number of rational points on curves over finite fields is $\#P$-complete - "Counting curves and their projections". Is it true for calculation of number of rational ...
18
votes
0answers
369 views

Checking Mertens and the like in less than linear time or less than $\sqrt{x}$ space

Say you want to check that $|\sum_{n\leq x} \mu(n)|\leq \sqrt{x}$ for all $x\leq X$. (I am actually interested in checking that $\sum_{n\leq x} \mu(n)/n|\leq c/\sqrt{x}$, where $c$ is a constant, and ...
4
votes
1answer
292 views

an algebraic variety for a boolean circuit

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$. I mean there is polynomial reduction $F$ such that for every boolean ...
1
vote
0answers
31 views

Reference requests for tiling easiness [closed]

For Wang tile problem, is there some general statements in a paper stating that the more tiles (supposed provided by random) available, the easier it is for these tiles to tile the plane? Thank you.
5
votes
1answer
119 views

Decidability of convex rearrangements of polygons

Triggered by the MO question, "How many convex shapes can be made with the pieces of the Stomachion?," I would like to pose this question: Q. Given $n$ polygons in a set $S$, say each with integer ...
15
votes
4answers
2k views

Languages beyond enumerable

A language is a set of finite-length strings from some finite alphabet $\Sigma$. It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings. ...
3
votes
2answers
74 views

Complexity of solving systems of linear diophantine equations

It is "well known" that a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$, $x\in \Bbb Z^n,b\in\Bbb Z^m$ for some $m,n \in \Bbb N$, can be solved in polynomial time, using Smith/Hermite Normal ...
7
votes
5answers
1k views

Zero knowledge proof of equality

Alice and Bob each secretly chooses an integer between 1 and 10, a and b. They want to know (with high probability) whether or ...
3
votes
0answers
115 views

Average nastiness of a Newton polytope

Given a Newton polytope $P$ inside the $d$-scaled simplex ( i.e $\alpha \in P \implies | \alpha |=d $ ), then we define the following quantity: $$ P(x)= \left( \sum_{\alpha \in P} ...
3
votes
1answer
585 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ ...
12
votes
2answers
205 views

Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
6
votes
2answers
182 views

Finding an “optimal” quotient in a free group

Consider the abelian free group $G = \mathbf{Z}^n$ of rank $n$ and a finite subset $A \subset G \setminus \{0\}$. Since $G$ is residually finite, there is a subgroup $H \subset G$ such that $A \cap H ...
2
votes
1answer
119 views

About Renyi entropy

If one is given a joint probability distribution over a finite set of discrete random variables then I guess there a notion of $\alpha-$Renyi entropy defined for it as $S_\alpha (X_1,..,X_n) = ...
3
votes
0answers
84 views

State of the art for univariate complex polynomials factorization with algebraic coefficients

Let $\mathbb{K}:=\overline{\mathbb{Q}}$ be the field of algebraic numbers. We choose to represent an element of $\mathbb{K}$ as its minimal monic polynomial, which is a vector in some $\mathbb{Q}^n$. ...
5
votes
0answers
115 views

Complexity of graph isomorphism

Last year, Laszlo Babai proved that the graph isomorphism problem can be solved in time: $$ \exp(O(\log^c n)) $$ where $n$ is the number of vertices. What is the best bound we have for $c$? (The ...
1
vote
0answers
128 views

How I can prove the equality $P^{P_{\operatorname{space}}}=NP^{P_{\operatorname{space}}}=P_{\operatorname{space}}^{P_{\operatorname{space}}}$ [closed]

I know how to prove that if $A \in P^{P_{\operatorname{space}}}$ then $A \in NP^{P_{\operatorname{space}}}$ and $A \in P_{\operatorname{space}}^{P_{\operatorname{space}}}$. I don't know how to prove ...
3
votes
0answers
247 views

Why is solving polynomial systems NP hard?

Solving polynomial systems is known to be a NP hard problem; however it is not completely clear to me where this complexity comes from. My interest is in the case of systems of multivariate ...
5
votes
6answers
732 views

Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $G$ then we can reduce the finding of a Hamiltonian cycle in $G$ to a Eurler your of $H$ ...
2
votes
1answer
233 views

Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?

Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in ...
25
votes
1answer
5k views

How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.807})$ for the multiplication of two $n \times n$ matrices (the exponent is $\frac{\log7}{\log2}$). ...
8
votes
1answer
323 views

Is there any real quadratic ring for which the Euclidean algorithm is polynomial?

We know from Rolletschek's work that the Euclidean algorithm of $\mathbb{Z}[i]$ is polynomial. Indeed, let $n$ be the maximum number of steps in the Euclidean algorithm applied to $u,v ...
7
votes
0answers
190 views

Can primes be (almost) random sequence in von Mises sense?

Random models for primes (such as Cramer's model) have been extensively used for informal justification of various conjectures involving primes. It is crucial to understand in what sense sequence of ...
5
votes
0answers
125 views

Complexity of $\mathbb{Z}^n$ tilings

Let $\mathcal{T} \subset \mathbb{Z}^n$ be a finite set. Let $\Lambda \subset \mathbb{Z}^n$ be a full rank lattice. We say that $\mathcal{T}$ is a $\Lambda$-tile for $\mathbb{Z}^n$ if the following ...
3
votes
0answers
74 views

What is the complexity of finding a third Hamilton Cycle in cubic graph?

According to Smith Theorem: if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known ...
4
votes
0answers
107 views

Littlewood-Richardson rule for the complete flag variety: GapP complete?

The cohomology ring of a complete flag variety $X$ has a basis of Schubert classes $S_u$ for permutations $u$. Define the Littlewood-Richardson coefficient $c_{uv}^w$ for permutations $u,v,w$ to be ...
1
vote
1answer
76 views

Graph colouring for bounded degree graphs

I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions, For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...
9
votes
2answers
264 views

Bounded Arithmetic vs Complexity Theory

In this post, when I talk about bounded arithmetic theories, I mean the theories of arithmetic according to "Logical Foundations of Proof Complexity", which capture the complexity classes between ...
3
votes
1answer
42 views

Complexity class of matrix generalization of knapsack problem

Let $n$ be a natural number, $u_+,v_+,u_-,v_-$ be real or complex column vectors of length $n$, and $M_1,M_2,\ldots,M_k$ be a finite collection of $n\times n$ real or complex matrices. Consider the ...
53
votes
3answers
4k views

What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this ...
2
votes
1answer
69 views

Directed edge-colouring

I'm interested to know whether the following problem is NP-complete or if there is an algorithm to solve it. Suppose we are given a directed graph $G=(V,E^{\rightarrow})$ and we want to colour the ...
1
vote
1answer
82 views

How to complete the NP-hardness proof of GENERAL-SQUARE-PRODUCT?

I am interested in the complexity of the following problem: GENERAL-SQUARE-PRODUCT INSTANCE: Two sets $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ of integers, a positive integer $k<n$ and a ...
6
votes
1answer
172 views

Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult. Is there a polynomial analog of this problem ...
1
vote
0answers
19 views

The complexity of Max-K interval selection

I came up with the following problem, but do not know how to analyze it. Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in ...
7
votes
1answer
147 views

Factoring a multiset into a product of two multisets

Given a multiset $S$ of $mn$ numbers, how hard is to find multisets $A$ and $B$, of $m$ and $n$ numbers respectively, such that $$ S = \{ xy \mid x\in A, y\in B \}~~~~\text{(multiset sense)}, $$ or ...
5
votes
1answer
443 views

Complexity of computing expansion of a newform level 18 weight 3 and character [3] - OEIS A116418

I am not familiar with newforms, so this may not make any sense. OEIS sequence A116418 is Expansion of a newform level 18 weight 3 and character [3] Numerical evidence suggest that up to $10^5$ $$ ...
14
votes
1answer
1k views

Is deciding if one planar graph is dual to another really NP-hard (Wikipedia claim)?

Wikipedia claims (permanent link) without reference: Testing whether one planar graph is dual to another is NP-complete. Another claim with reference: For any plane graph G, the medial graph ...
6
votes
0answers
180 views

Complexity of approximating the size of the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$ It is NP-hard to compute $S_M$ exactly I believe by applying the ...