Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
4answers
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
1answer
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
1answer
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
2answers
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
1answer
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
3answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
9answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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 ...