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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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.

3
votes
1answer
85 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 ...
27
votes
1answer
712 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 ...
1
vote
2answers
138 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 ...
10
votes
1answer
389 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 ...
11
votes
3answers
455 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?
1
vote
1answer
36 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
234 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
33 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
159 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
141 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
83 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-...
6
votes
1answer
185 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
62 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
106 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 ...
87
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
140 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
91 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
59 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^{...
1
vote
0answers
31 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
627 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
73 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
51 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
54 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
37 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
87 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
17 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
79 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
155 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
129 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
103 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
68 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 ...
1
vote
2answers
203 views

On complexity of a combinatorial number theoretic problem?

Given the matrix $\begin{bmatrix} r_{11}&\dots&r_{1n}\\ \vdots&\ddots&\vdots\\ r_{m1}&\dots&r_{mn} \end{bmatrix}\in\Bbb Z^{m\times n}$ with $0<r_{ij}<2^n$ and $a,q\in\...
0
votes
0answers
37 views

Minimum space needed to compute a binomial coefficient

What is the minimum space required by an algorithm that, given as input two integers $n \geq k \geq 0$, performing only integer operations of addition, subtraction, multiplication, and division, ...
4
votes
1answer
141 views

Time Complexity of the Word Problem for Finite Permutation Groups

Given a finite permutation group, i.e. a subgroup of the symmetric group on $n$ symbols in terms of generators, what is the complexity of the word problem? That is, computing if two words in the ...
1
vote
1answer
72 views

Complexity to decide for permutation group if every element fixed at most $k$ points

I want to consider the following problem, which generalises the decision problem to decide if a given finite permutation group is a Frobenius group: Given a finite permutation group in terms of its ...
1
vote
2answers
117 views

Complexity of decision problem to decide if permutation group is $k$-transitive

Given a finite permutation group $G$ (a subgroup of the symmetric group on a finite set) in terms of its generators, what is known about the decision problem of deciding if $G$ is $k$-transitive for a ...
0
votes
0answers
60 views

About Rademacher complexity

The following two questions of mine might be related, Q1 Are there examples of non-trivial function classes known in which some norm bound (like the $L^p$ norm) can be used to carve out a subset of ...
0
votes
0answers
40 views

Incompressibility formulations of computational complexity conjectures

Allender's paper, Curiouser and Curiouser: The Link between Incompressibility and Complexity, investages the connections between Incompressibility notions in computability theory and complexity ...
1
vote
0answers
48 views

Complexity of conic optimization problems

I am interested in bounding the computational complexity of the interior points method for solving a generic conic problem of the form \begin{equation} \min_x \left\{ c^T x : \mathcal{A}x-B\in\mathbf{...
1
vote
0answers
75 views

computing number of primes with congruence constraint

Suppose I give you $(a, b, M)$ and ask you to compute the number of primes not exceeding $M$ which are congruent to $b$ mod $a.$ What is the most efficient way of doing it? (without congruence ...
1
vote
1answer
102 views

Connections between algebraic semantics and computational complexity of a logic?

I'm re-posting this question from cstheory.SE hoping to have more luck. I'm a computer scientist learning a bit about algebraic logic and I was wondering how knowing the algebraic semantics of a ...
1
vote
0answers
32 views

How is the minimax oracle used to find the oracle complexity of projected subgradient?

I am going through a set of blog posts on the complexity of projected gradient method. https://blogs.princeton.edu/imabandit/2013/03/15/orf523-oracle-complexity-large-scale-optimization/ defines the ...