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)

14
votes
0answers
318 views
+50

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 ...
5
votes
1answer
112 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 ...
4
votes
1answer
284 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
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.
15
votes
4answers
1k 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
70 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
113 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} ...
12
votes
2answers
200 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
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
1answer
113 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
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
0answers
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
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
238 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 ...
8
votes
1answer
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
0answers
184 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
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
0answers
70 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
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
2answers
249 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 ...
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 ...
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 ...
7
votes
1answer
145 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 ...
1
vote
0answers
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 ...
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 ...
6
votes
0answers
178 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 ...
3
votes
1answer
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 ...
6
votes
2answers
244 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 ...
3
votes
1answer
194 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
0answers
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} ...
3
votes
1answer
125 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 ...
1
vote
1answer
75 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 ...
3
votes
0answers
21 views

Complexity of OBDD isomorphism (representing same function after permutation of variables)?

According to wikipedia Ordered Binary Decision Diagarams (OBDD) are a data structure that is used to represent a Boolean function. OBDD is a DAG with two sinks $0,1$. The size of the BDD is number ...
2
votes
1answer
222 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 ...
2
votes
0answers
169 views

Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time. (1) Is there any ...
3
votes
1answer
570 views

Claimed Quadrature Results seem Impossible

We've been preparing a preprint that shows that the convergence bounds proved for tanh-sinh quadrature for numerical integration, cannot possibly hold, and an error must exist - since they imply a P ...
5
votes
1answer
281 views

Division by $n$ in elliptic curves

Let $E/\mathbb F_{p^m}$ be an arbitrary elliptic curve over the Galois field $\mathbb F_{p^m}$, and let $$[n]^{-1}(P)\cap E(\mathbb F_{p^m})=\{Q\in E(\mathbb F_{p^m})\mid nQ=P\}.$$ Also let ...
11
votes
3answers
400 views

Algorithmic complexity of formal proof verification?

In this question, suppose $S$ is some popular real-world automated proof system that is stronger than or equivalent to Peano Arithmetic. I would be happy with a positive answer to the following for ...
2
votes
1answer
52 views

Complexity of recognizing equivalent translation surfaces

"A translation surface is a union of polygons with pairs of parallel edges identified by translation, up to cut and paste equivalence." I take that succinct (and not fully precise) definition ...
4
votes
1answer
83 views

Complexity of this minimization

For integer $N$ consider the mapping $$f : (0,1)^N \to \mathbb{R}, \quad x \mapsto \min_{b \in \{0,1\}^N} \left\{ x^b + x^{1-b} \right\},$$ where $x^b = x_1^{b_1} \cdots x_N^{b_N}$ and $1-b = (1-b_1, ...
4
votes
1answer
285 views

Complexity of linear solvers vs matrix inversion

Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...
1
vote
1answer
180 views

On Knot Equivalence problem statement

How is the knot equivalence problem represented? By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with ...
16
votes
1answer
1k views

Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
1
vote
0answers
46 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
0answers
53 views

Complexity theory and closed form formulas in analysis

My question concerns definitions of "closed form" solutions. In hamiltonian systems this is closely related to complete integrability. In this context closed form can refers to having $(q(t),p(t))$ ...
2
votes
2answers
263 views

Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...