# Tagged Questions

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 an so on.

**0**

votes

**0**answers

71 views

### How to evaluate the order of magnitude of a complex sum? [on hold]

$\sum^{\log N}_{i=1}\frac{3i^2}{4^i-1}$
What's the order of magnitude of the sum above? such as $O(\log N)$?
How to calcluate?

**27**

votes

**2**answers

932 views

+100

### A curious process with positive integers

Let $k > 1$ be an integer, and $A$ be a multiset initially containing all positive integers. We perform the following operation repeatedly: extract the $k$ smallest elements of $A$ and add their ...

**1**

vote

**1**answer

74 views

### How many iterations the best biprime factoring method has to factor a number [closed]

I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...

**5**

votes

**0**answers

71 views

### Combinatorial region-halfplane incidence structures

I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate.
Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...

**8**

votes

**0**answers

99 views

### Known obstruction for efficient computation of Stable homotopy groups?

Computation of stable homotopy groups (for example of sphere) is hard, but still, not as hard as unstable ones.
For unstable homotopy groups there are some results showing that there cannot be ...

**1**

vote

**0**answers

93 views

### $\mathrm{NP}$-complete problems in graph theory: undirected vs. directed

Is it true that it is much easier to establish $\mathrm{NP}$-complete on undirected graphs than digraphs (directed graph)?
Academic articles proving $\mathrm{NP}$-completeness of problems on ...

**2**

votes

**1**answer

89 views

### Matching two sequences between each other

Given the sequence of symbols $A$ (contains ~10,000 symbols) and sequence of blocks $B$ (contains ~3,000 blocks, ~30 symbols inside each block) I need to exclude some blocks from sequence $B$ so that ...

**1**

vote

**0**answers

50 views

### Computational complexity for spectral radius of symmetric matrix

What is the best known algorithmic complexity for computing the spectral radius (largest eigenvalue in magnitude, possibly with respect to some precision and confidence) of a symmetric matrix of size $...

**2**

votes

**0**answers

84 views

### Algorithm detecting all distinct k-th powers in a string for all k ≥ 3

In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$.
The ...

**0**

votes

**0**answers

77 views

### How well does convolution model $\mathbb Z$ multiplication?

In $\mathbb K[x]$ or $\mathbb K$ where $\mathbb K$ is a ring we can think of multiplication of polynomials as convolution. Over $\mathbb Z$ this line of thought has led to fast integer multiplication ...

**7**

votes

**4**answers

456 views

### What would $\mathcal{P} \neq \mathcal{NP}$ tell us about some non-constructive proofs?

Let me sum up my - hopefully correct - understanding of the travelling salesman problem and complexity classes. It's about decision problems:
"[...] a decision problem is a problem that can be ...

**3**

votes

**1**answer

134 views

### Higher roots modulo prime complexity best algorithm

Given integers $a,\ell$ and prime $p$ we need to find the roots of the algebraic equation $x^\ell\equiv a\bmod p$. We know there are at most $\ell$ such $x$.
What is the best method to find all such ...

**30**

votes

**1**answer

925 views

### Is this conjecture strictly weaker than P=NP?

My three computability questions are related to the following group theory question (first asked by Bridson in 1996):
For which real $\alpha\ge 2$ the function $n^\alpha$ is equivalent to the Dehn ...

**2**

votes

**2**answers

155 views

### Time functions of non-deterministic Turing machines (a better question)

This is a more precise version of that question.
Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation ...

**11**

votes

**1**answer

415 views

### Real numbers with given complexity

This may be an easy question or it may be related to a well known open problem in Computer Science.
Let $\alpha>0$. We say that $\alpha$ is computed in time $T(n)$ if there is a Turing machine ...

**12**

votes

**3**answers

485 views

### Determining if some permutation of a vector satisfies a system of linear equations

Let $A$ be a matrix and $x$ a fixed vector. How can we determine whether or not there exists a permutation matrix $P$ such that $APx=0$? Does this problem reduce to anything well-understood?

**2**

votes

**1**answer

70 views

### Level sums, displacements: how to determine them efficiently?

Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$,
$\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$.
Define $$S(\delta,m) = ...

**5**

votes

**1**answer

245 views

### Time functions of non-deterministic Turing machines

Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$. The smallest ...

**2**

votes

**2**answers

41 views

### Complexity of 2D-Minkowski sum of non-convex polygons

I have read that the complexity of computing the Minkowski-Sum of $2$ non-convex polygons (through convex decomposition) is $O(m^2 n^2)$, where $m$ and $n$ is the number of vertices of each polygon. ...

**4**

votes

**1**answer

165 views

### What is the time complexity for solving Diophantine equations of degree 2?

Manders and Adleman mention that the computational complexity for binary quadratic Diophantine equations is NP-complete. Has a more specific complexity been claimed for polynomials of the form $Axy + ...

**2**

votes

**1**answer

160 views

### Is this partition problem strongly NP-complete?

Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...

**3**

votes

**2**answers

84 views

### Is there an efficient way to represent all non-simple cycles of a digraph up to the number of vertices?

Given two digraphs $G$ and $H$, I want a method for creating a bijection between all non-simple cycles of for all $n \le |V(G)|$. That means, given $C_G(n)$ and $C_H(n)$ being the sets of all non-...

**7**

votes

**1**answer

192 views

### What is the complexity of determining if a knot group is $\mathbb{Z}$?

It is known from the work of Waldhausen that the isomorphism problem for knot groups is decidable. What is then:
The complexity of determining if a knot group is $\mathbb{Z}$? .i.e. same as the ...

**1**

vote

**0**answers

47 views

### descriptive complexity theory to attack computational complexity problems [closed]

What is the usefulness of descriptive complexity to attack computational complexity theory?what are the recent results in this direction? Thanks

**1**

vote

**0**answers

63 views

### Bipartite clustering is NP-hard?

Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...

**12**

votes

**0**answers

114 views

### Straight-line drawing of regular polyhedra

Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane). For example, the ...

**89**

votes

**9**answers

11k views

### On Mathematical Arguments Against Quantum Computing

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...

**2**

votes

**0**answers

150 views

### Factoring problem similar to $RSA$ structure that is possibly not $NP$ complete and not $coNP$ also?

Standard factoring problem $\Pi_1$ is 'Given integers $N$ and $M$ is there a factor $d\in[1,M]$ of $N$?'. This is in $NP$ since such a factor is the witness and in $coNP$ since one can check all the ...

**1**

vote

**0**answers

97 views

### Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it?
Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...

**0**

votes

**0**answers

63 views

### Faster Mixed Integer Linear Programming Searchless Feasibility

We know Lenstra's Mixed Integer LP with Kannan's modificiation solves feasibility Mixed Integer LP in $n$ integer variables, $r$ real variables and $m$ constraints by solving the search version in $n^{...

**2**

votes

**0**answers

36 views

### Complexity of computing roots in general rings

The Rabin Cryptosystem derives its basic security assumption on the observation, that computing roots in integer modulo $n$ rings, is as hard as finding the prime decomposition of $n$.
Mathematically ...

**21**

votes

**2**answers

637 views

### Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class.
Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...

**0**

votes

**1**answer

74 views

### Maximum partition of bipartite graph

Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...

**3**

votes

**1**answer

54 views

### Incomparable NPI decision problems

Assume that there exists at least one NP-intermediate decision problem (which, by Ladner's theorem, is equivalent to P being distinct from NP).
Do there exist two NP-intermediate decision problems, $...

**0**

votes

**0**answers

56 views

### Number of bits in square representation in sieve techniques?

In quadratic sieve and number field sieve $x,y\in\mathbb Z$ is solved in congruence $x^2\equiv y^2\bmod N$. Is there an estimate on typical sizes (number of bits in integers) of $x,y$ in these methods ...

**0**

votes

**0**answers

34 views

### On CNF forms with weight $d$ satisfying instances

Given literals $x_1,\dots,x_n$ how many clauses $C_1,\dots,C_m$ does one need of the type $C_i=y_j\vee y_k\vee y_l$ where $y_l\in\{x_l,\overline x_l\}$ such that the CNF form $C_1\wedge\dots\wedge C_m$...

**1**

vote

**1**answer

70 views

### Non-invertible Karp reduction

Karp (many-one) reducibility between $NP$-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$. Berman-Hartmanis ...

**2**

votes

**0**answers

38 views

### Clarification on FPTAS optimization in a paper

In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...

**0**

votes

**0**answers

89 views

### Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$?

We got an argument that 3-coloring bounded degree graphs is subexponential
with complexity $O(\exp{(\sqrt{n}\log^2{n})})$.
The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$
and 3-...

**0**

votes

**0**answers

18 views

### Constructing integers with precise number of factors

Using randomness in polylog(n) arithmetic operations we can construct an integer with O(n) bits that has no other factors other than 1 and itself. Given integer m what is known about constructing ...

**2**

votes

**0**answers

80 views

### what is the relationship between the complexity of a function and the complexity of it's graph set?

Given $f: \omega \rightarrow \omega$ , what is the relationship between the following two notions:
(i) the computational complexity of f (in the standard sense, say with naturals represented in ...

**0**

votes

**0**answers

7 views

### Fixed dimension Integer programming minus LLL in $NC$?

If you remove LLL part then is remaining part of
Lenstra algorithm
Barvinok algorithm
in $NC$ in fixed dimension?

**1**

vote

**1**answer

159 views

### Bit complexity of Barvinok's algorithm

I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension.
What exactly is this arithmetic complexity?
...

**0**

votes

**0**answers

70 views

### How hard is gapped satisfiability?

It is well known that general satisfiability (of polynomially many clauses) is NP-hard, and in fact, it is conjectured that an algorithm deciding instances of SAT takes time nearly $2^n$ on $n$ ...

**4**

votes

**1**answer

131 views

### What is the fastest way of finding a complement?

I am given a direct factor $N$ which is a normal subgroup of a group $G$. I want to find a complement of $N$ in $G$. The model of computation is RAM. It takes $O(n)$ time to find an inverse of one ...

**1**

vote

**0**answers

35 views

### Is there a problem that can be solved in each of a nested sequence of resource constraints, but not in their intersection?

For example, is there a problem such that $\forall\varepsilon>0$ there is a $O(n^{1+\varepsilon})$-time algorithm to solve it, but which cannot be solved by a single algorithm which runs in $O(n^{1+...

**0**

votes

**1**answer

110 views

### Is there fast algorithm for 3SUM?

Is there algorithm for 3SUM which have complexity O(n) or O($n^{3/2}$) for randomly chosen input with bit length of maximum number approximately equal to count of input numbers?

**3**

votes

**0**answers

71 views

### Deterministic procedure to find irreducible polynomials

In $\Bbb F_q[x_1,\dots,x_n]$ given $d_1,\dots,d_n\in\Bbb N$ is there a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=\max_{i\in\{1,\dots,n\}}d_i$ and $d_i=deg(...

**3**

votes

**1**answer

147 views

### Algorithms for Fixing Sudokus

Suppose someone got stuck solving a Sudoku and asks you to figure out, what went wrong. Unfortunately that person only sends you a copy of the instance, where you neither see which of the numbers ...

**0**

votes

**0**answers

41 views

### Formalizing a projective additive construction of polytopes?

Given a polytope represented by $$Ax\leq b$$ where $A\in\Bbb Z^{m\times n}$, $x\in\Bbb Z^n$ and $b\in\Bbb Z^m$ with $N\geq 0$ number of integer points can we construct a polytope with $N+1$ integer ...