# Questions tagged [computational-complexity]

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

**2**

votes

**1**answer

74 views

### Are there any continuous-time stochastic processes in which transition probabilities are discontinuous functions over time?

In stochastic processes, like homogeneous Markov processes, Poisson processes, Queueing systems etc., the functions that represent (transition) probabilities are continuous over time. This is also ...

**1**

vote

**0**answers

17 views

### Existence of Costas array with specified displacment vectors?

Costas array is a set of $n$ points lying on the square of a $n×n$ checkerboard, such that each row or column contains only one point, and that all of the $n(n − 1)/2$ displacement vectors between ...

**3**

votes

**1**answer

260 views

### does recursive (decidable) languages closed under division (Quotient) with any language?

I need to prove or disprove that R languages are closed under divison.
I have managed to prove thet CFL are't closed under division. I read in wikipedia that RE languages are closed, but I didn't find ...

**0**

votes

**0**answers

48 views

### Calculating the time complexity of a recursive function [closed]

I posted a problem on stack overflow for which a brilliant solution has been provided. What could be the time complexity of this solution?

**1**

vote

**0**answers

33 views

### Shortest Lattice Vector with restricted $x$

Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...

**3**

votes

**1**answer

81 views

### Is coprimality in $NC$?

Following reference https://pdfs.semanticscholar.org/e86e/8d7a267a29b9ad4ca112828109adfec55e8b.pdf claims integer coprimality is in $NC$ and it also has one citation. Is this claim valid?

**8**

votes

**0**answers

131 views

### Primitive recursive and feasible presentations for nonstandard models of arithmetic

Let us define a countable model $\cal{M}$ = $(M,+_M ,\cdot_M, <_M)$ of $Q$ (Robinson arithmetic) to have a (primitive) recursive presentation if $\cal{M}$ is isomorphic to $(\omega, \oplus, \...

**1**

vote

**0**answers

93 views

### Is it known whether $\mathrm{NP \subseteq P/poly}$?

It is not immediately clear to me whether this statement is true or false. Can finite restrictions of NP problems be computed in polynomial time?

**2**

votes

**1**answer

84 views

### The complexity of sorting a list having one free cell

Making a standard bureocracy (using Word tables), I arrived to the following
Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say ...

**2**

votes

**0**answers

42 views

### Karp hardness of two cycles which lengths differ by one

Our problem is as follows:
NEARLY-EQUAL-CYCLE-PAIR
Input: An undirected graph $G(V,E)$
Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO
Is ...

**5**

votes

**1**answer

67 views

### What is the complexity of counting Hamiltonian cycles of a graph?

Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard.
Is it also $PP$-hard in the sense ...

**1**

vote

**2**answers

111 views

### Computational complexity of sizes and number of orbits of a group acting on a set

I'm interested in the relation between the computational complexity of counting orbits and counting elements in orbits for groups acting on sets. More formally:
Assume that $X_n$ is a infinite ...

**4**

votes

**1**answer

104 views

### What is the minimum worst-case length of an element removal game?

A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that ...

**2**

votes

**0**answers

51 views

### Quantum versus classical communication complexity

Problem. Is it true that any 2-party communication problem $f(x,y)$ of poly-logarithmic complexity in the quantum simultaneous message passing model ($Q''$) has complexity $n^{o(1)}$ (i.e., strongly ...

**6**

votes

**0**answers

102 views

### Does the problem of recognizing 3DORG-graphs have polynomial complexity?

A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...

**42**

votes

**4**answers

2k views

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

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

**6**

votes

**0**answers

80 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 $\...

**10**

votes

**0**answers

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

**2**

votes

**0**answers

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

**3**

votes

**1**answer

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

**2**

votes

**0**answers

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

**3**

votes

**0**answers

91 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

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

**8**

votes

**4**answers

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

**4**

votes

**1**answer

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

**31**

votes

**1**answer

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

**3**

votes

**2**answers

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

**12**

votes

**1**answer

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

**14**

votes

**3**answers

580 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?

**3**

votes

**1**answer

73 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) = ...

**6**

votes

**1**answer

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

**3**

votes

**2**answers

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

**5**

votes

**1**answer

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

**3**

votes

**1**answer

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

**4**

votes

**2**answers

88 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

198 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

48 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

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

**16**

votes

**0**answers

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

**93**

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

**3**

votes

**0**answers

166 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

103 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

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

**22**

votes

**2**answers

696 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

75 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,\...

**4**

votes

**1**answer

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