**9**

votes

**0**answers

295 views

### Why should Algebraic Geometers and Representation Theorists care about Geometric Complexity Theory?

Geometric Complexity Theory has demonstrated that Complexity Theorists should care about Algebraic Geometry and Representation Theory, but, why should Algebraic Geometers and Representation Theorists ...

**1**

vote

**1**answer

89 views

### $0/1$ programming multiple quadratic constraints

If we have an $n$-variable rank $n$-linear system it is clear we can find whether there exists a $0/1$ solution in polynomial time.
If we have an $n$-variable degree $2$ system how many constraints ...

**5**

votes

**1**answer

97 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 \...

**2**

votes

**0**answers

56 views

### Effective “almost enumeration” of monotone boolean functions

Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$.
Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that:
1) $k = \log |\...

**1**

vote

**1**answer

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

**1**

vote

**0**answers

53 views

### Recognizing cubic graphs decomposable into 2-factor with given cycle type

Petersen's theorem states that every cubic, bridgeless graph contains a perfect matching. It implies that the edge set $E$ can be partitioned into a perfect matching and a 2-factor.
Determining the ...

**1**

vote

**0**answers

323 views

### Is this minimization problem NP-Complete ?

We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.
...

**0**

votes

**0**answers

75 views

### Generating set of Graph-Automorphism from Direct Product

Notation:
$H$ is the adjacency matrix of graph $\mathcal{H}$ .
$$H = \begin{bmatrix}
H_{(3)} & R_{(3, 2)} & R_{(3,1)} \\
R_{(3,2)} & H_{(2)} & R_{(2,1)} \\
R_{(3,1)} & R_{(2,1)}...

**0**

votes

**0**answers

19 views

### Counting contingency tables with unary inputs

Given $2$ sequences $A = (a_1,\dots,a_k)$ and $B = (b_1,\dots,b_l)$ of natural numbers. A contingency table is a matrix in $\mathbb{N}^{k \times l}$ with row sums $A$ and column sums $B$.
Counting ...

**0**

votes

**0**answers

62 views

### GI-hard problems that would benefit from efficient algorithm for GI

The exponential time hypothesis (ETH) states that 3SAT can not be solved in subexponential time. As far as I know, it is not known whether an efficient algorithm for graph isomorphism problem (GI) ...

**19**

votes

**4**answers

2k views

### How do we know that P != LINSPACE without knowing if one is a subset of the other?

I've seen that P != LINSPACE (by which I mean SPACE(n)), but that we don't know if one is a subset of the other.
I assume that means that the proof must not involve showing a problem that's in one ...

**5**

votes

**2**answers

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] = svds(...

**10**

votes

**2**answers

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

**8**

votes

**0**answers

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

**40**

votes

**3**answers

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

**0**answers

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

**0**

votes

**0**answers

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

**0**answers

57 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

**0**answers

48 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

**3**answers

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

**-3**

votes

**1**answer

129 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

**2**answers

716 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, symbol{-}to{-}...

**1**

vote

**0**answers

64 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

**0**answers

374 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

**1**answer

295 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

**0**answers

32 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

**1**answer

125 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

**4**answers

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

**2**answers

80 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

**5**answers

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

**0**answers

116 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} \binom{d}{\alpha}...

**3**

votes

**1**answer

649 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

**2**answers

208 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

**2**answers

186 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

**1**answer

123 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) = \frac{...

**3**

votes

**0**answers

86 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

**0**answers

119 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

**0**answers

130 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

**0**answers

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

**6**

votes

**6**answers

775 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

**1**answer

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

**27**

votes

**1**answer

6k 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

**1**answer

326 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 \in\mathbb{Z}[i]...

**7**

votes

**0**answers

194 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

**0**answers

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

**0**answers

84 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

**0**answers

110 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

**1**answer

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

**2**answers

271 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 $AC^...

**3**

votes

**1**answer

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