**7**

votes

**2**answers

631 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

**0**answers

52 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

356 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

290 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

30 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

115 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

71 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

114 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

**1**answer

531 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$ ...

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

**12**

votes

**2**answers

203 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

179 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

114 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

**0**answers

83 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

111 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

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

**0**answers

239 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

**6**answers

695 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

226 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

**1**answer

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

**1**answer

322 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

**0**answers

185 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

123 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

72 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

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

**1**answer

74 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

251 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

**1**answer

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

**52**

votes

**3**answers

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

**1**answer

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

**1**answer

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

**1**answer

171 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

**0**answers

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

**1**answer

146 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

**1**answer

442 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

**1**answer

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

**0**answers

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

**1**

vote

**0**answers

39 views

### Bit complexity versus arithmetic complexity of polynomial multiplication

Given degree $d_1$ and $d_2$ polynomials in $\Bbb Z[x]$ with coefficient sizes of bits $b_1$ and $b_2$ respectively
(1) what is the bit complexity of multiplying the two polynomials?
(2) What is ...

**3**

votes

**1**answer

57 views

### Complexity of counting MAXCUT in planar graphs — seemingly contradicting claims

Confusion is likely. Appears to me two papers give contradicting claims
about the complexity of counting MAXCUT in planar graphs.
Exact Max 2-SAT: Easier and Faster p. 6
However, counting the ...

**2**

votes

**1**answer

439 views

### Complexity of bipartite graphs and their matchings.

My question concerns a hypothetical family of bipartite graphs, $G_i$.
Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled
by their color and a binary string of ...

**6**

votes

**2**answers

249 views

### Variation on the Subset Sum Problem

Given a nonempty set of integers, and given that there exists a subset of this set whose elements sum to zero, is finding the smallest such subset NP-complete?
Disclaimer: The above question ...

**28**

votes

**7**answers

3k views

### Can a problem be simultaneously polynomial time and undecidable?

The Robertson-Seymour theorem on graph minors leads to some interesting conundrums.
The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...

**3**

votes

**1**answer

195 views

### Polynomial factoring over finite fields

What is known in general about the complexity of factoring polynomials over finite fields?
For instance given $\Bbb F_q$ where $q=p^n$ and total degree $d$ polynomial in $m$ variables what can we say ...

**1**

vote

**0**answers

26 views

### Some confusion regarding the definition of NPO reduction

I've seen the following definition in a paper on approximation preserving reductions.
Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} ...

**1**

vote

**0**answers

227 views

### VC dimension and boolean hypercube subgraphs

Are there any well studied graph theoretic properties that are common to all subgraphs of the boolean hypercubes that have a given VC dimension d.

**1**

vote

**1**answer

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

**4**

votes

**1**answer

127 views

### Weak Bounded Arithmetics

Let $\Sigma^b_i$ and $\Pi^b_i$ formulas be bounded formulas defined by Buss in language of $L_b$. $PIND(\phi(x))$ is the formula:
$$\phi(0)\land \forall x(\phi(\left \lfloor \frac{x}{2} \right ...

**16**

votes

**2**answers

1k views

### Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...