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; Kolmogorov Complexity and so on.
1,369 questions
-4 votes
0 answers
35 views
A scalene triangle with all four centres having integral values [closed]
Requirements A triangle need be scalene or obtuse This property is already shown and proven in right angled triangle
-1 votes
0 answers
31 views
Obstructions to size-independent coercivity/spectral gaps in continuous embeddings of NP-complete CSPs
Let $\mathcal{I}$ be instances of a fixed NP-complete CSP (e.g., 3-SAT with $N$ variables and $M$ clauses). Suppose each instance $I \in \mathcal{I}$ is mapped to a pair $(\Omega_I, E_I)$ where $\...
- 493
8 votes
1 answer
368 views
Computational complexity of a preorder of commutativity conditions
Say that a $k$-ring is a ring in which $x^k=x$ for all $x$, and write $m\trianglelefteq n$ iff every $m$-ring is an $n$-ring. It's not hard to show (see the end of this answer) that $\trianglelefteq$ ...
- 19.5k
2 votes
0 answers
101 views
Calculating Polynomial Resultants Quickly
I'm working on a project that requires quickly calculating the resultant of two polynomials in $\mathbb{Z}[x]$ of large degree $d,e$. On the Wikipedia article for polynomial resultants, it says that ...
- 181
9 votes
0 answers
555 views
Is it hard to decide if two codes have the same weight enumerator polynomial?
Consider the following decision problem, which we will call COMPARE. We are given as input a pair $(V_0, V_1)$ of linear codes in $\mathbb{F}_2^n$, and asked to decide whether $V_0, V_1$ have the same ...
- 401
1 vote
2 answers
314 views
Algorithms to count restricted injections
Let the following data be given. Two positive integers $m$ and $n$. A family of sets $B_a \subseteq \{1, \dots, n\}$ (for $a \in \{1, \dots, m\}$). The task is to count the number $N$ of injective ...
- 143
4 votes
1 answer
146 views
Complexity of the clause fragment of propositional Łukasiewicz logic
Disclaimer: this is a repost of a MS question with the same title — https://math.stackexchange.com/questions/5072398/complexity-of-the-clause-fragment-of-%c5%81ukasiewicz-logic People who know the ...
1 vote
0 answers
114 views
How big can a multiprojective variety be for which Macaulay2 can calculate irreducible components and check their smoothness?
I have a multiprojective variety $X$ in a product of projective spaces given by a multigraded ideal $I$. Suppose that the multiprojective variety is embedded into a product of projective spaces the ...
- 3,432
1 vote
1 answer
223 views
Evaluating the weight enumerator polynomial at special points
Let $C\subseteq\mathbb{F}_2^n$ be a linear code and let $P$ be the corresponding weight enumerator polynomial. That is, $$P(x)=a_nx^n+\cdots+a_1x+a_0$$ where, for $0\leq j\leq n$, we have $a_j:=\#\{v\...
- 401
18 votes
2 answers
495 views
Number fields in fast matrix multiplication
A common approach to construct fast multiplication algorithms is to make an ansatz for the matrix multiplication tensor of fixed dimension and rank (e.g. $2 \times 2 \times 2$ and rank $7$ if we want ...
- 2,602
0 votes
1 answer
176 views
Computational hardness of ordering problem inducing even and odd sums
I am interested in the complexity of a computational problem I encountered while studying Quran. We are given a sequence of positive integers $a_i$, we want to order them and find sums of pairs $a_{\...
- 3,035
5 votes
1 answer
308 views
Hardness of comparing weight partitions of an affine space over $\mathbb{F}_2$
Let $A$ be an affine subspace of $\mathbb{F}_2^n$. Let $m\leq n$ and $Q_0, Q_1$ be linear maps $\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m$. Consider the following decision problem: Decide whether or not ...
- 401
93 votes
28 answers
21k views
Which popular games have been studied mathematically?
I'm planning out some research projects I could do with undergraduates, and it struck me that problems analyzing games might be appropriate. As an abstract homotopy theorist, I have no experience with ...
5 votes
3 answers
604 views
Self-evident truths in Computational Geometry
I needed to use Computational Geometry result citations for my article. The article topic is Machine Learning. Some of citations I found, but for others it appears that they belong to so called "...
- 79
0 votes
0 answers
107 views
Terminology: commonly used name for an $\omega$ machine?
I am writing an expository essay on certain aspects of mathematical proofs, and one recurring pattern is the kind of question which is short in one direction but long in the other. A couple of ...
- 109
1 vote
0 answers
213 views
Reduce linear code minimum distance to lattice closest vector (CVP)
There are many NP-complete problems, e.g. SAT, CVP, SIS, graph colouring, Minesweeper etc. By definition there are polynomial time reductions from one to another of these, at least in their decision ...
- 273
2 votes
0 answers
163 views
Understanding monomial cancellation in $f^2$ for sparse polynomials with bounded individual degree
Let $f(x_1, \dots, x_n)$ be an $s$-sparse polynomial over a field $\mathbb{F}$, where each variable has individual degree strictly less than $d$ (i.e., $\deg_{x_i}(f) < d$ for all $i$). When we ...
5 votes
2 answers
821 views
In Euclidean space, if it's easy to generate random elements of a set, is it also easy to compute the projection to the set?
Let $A \in \mathbb{R}^m$ be some set with the property that it is easy (polynomial-time computation) to generate random elements $r \in A$. Is it then also easy to compute $$ P_A(x) := \arg \min_{y\in ...
- 1,173
15 votes
1 answer
693 views
The most efficient algorithm for finding a root of a polynomial over finite field
I have a polynomial of degree around $2^{35}$ over a finite field $\mathbb{F}_p$, where $p$ is a 64-bit prime number. What is the most efficient algorithm for finding a root of such a polynomial? (...
- 151
2 votes
0 answers
159 views
Best time complexity upper bounds for Graph Isomorphism problem of several graphs / digraphs classes of bounded degrees
I am interested in knowing the best complexity upper bounds for the following graph isomorphism problems (best theoretical deterministic upper bound). For some of those I already have some references (...
- 63
1 vote
1 answer
102 views
Can the CVP -> OptCVP reduction be extended to lattices with real basis?
In Theorem 8 of Micciancio’s lecture notes, a reduction from the Closest Vector Problem (CVP) to its optimization version (OptCVP) is given under the assumption that the lattice basis $B \in \mathbb{Z}...
- 21
3 votes
0 answers
141 views
How fast can we solve SVP using an SVP$_{\gamma}$ subroutine?
An $n$ dimensional lattice is the set of integer linear combinations of $n$ linearly independent vectors in $\mathbb{R}^{d}$ ($d\le n$). The $n$ independent vectors are called the basis of the lattice,...
- 169
0 votes
1 answer
241 views
A variant of max-flow problem
Consider the following variant of the max-flow problem. We are given a set of flows and a network modelled by a graph. Each edge of the graph can accept only a subset of flows, which is different from ...
- 327
1 vote
1 answer
338 views
Polynomial Time Algorithm for Solving Diophantine Equation with large integer number
My question is Is there an algorithm in polynomial time that can find solutions $(x,y,k)$ to the Diophantine equation $$ x^2 + k y^2 = N$$ where $x,y,k$ are unknow integers, $N$ is known, but its ...
- 129
16 votes
0 answers
467 views
What was Gill and Ladner’s joke about P=NP?
Comments on this question point out that John Gill (of the famous Baker–Gill–Solovay paper) lists a joke on his online CV: A Joke about P =?NP Gill, J., T., Ladner, R. 1973 Googling, I can’t find ...
- 23.1k
5 votes
0 answers
183 views
Hard word problems for natural groups
Are there known examples of naturally-occurring groups where the word problem is algorithmically solvable but not easily? I ask because I'm looking at word problems of some groups of interest to me, ...
- 6,934
0 votes
0 answers
76 views
Minimal finite-edit shadowing distance in the full two-shift
Let $\Sigma_2 = \{0,1\}^{\mathbb{Z}}$ be the full two-shift with left-shift map $\sigma$ and the standard product metric $$d(x,y) = 2^{-\inf\{|n| : x_n \neq y_n\}}.$$ Fix $\varepsilon = 2^{-m}$ for ...
1 vote
2 answers
225 views
Testing planarity algebraically by reduction to counting problem reducible to determinant computation
Given a graph, is there a way to count the number of 'non-equivalent' obstructions to planarity to the given graph? Can this be done efficiently algebraically such as can we reduce this problem to ...
- 1
10 votes
2 answers
3k views
MIP*=RE theorem and its impact on logic and proof theory
In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
- 9,634
18 votes
1 answer
1k views
(Very) Large numbers, Chaitin's incompleteness theorem and a specific upper bound
Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>...
- 9,634
6 votes
2 answers
373 views
Extending polynomial hierarchy above $\omega$
The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the ...
- 3,987
1 vote
0 answers
112 views
Rough numerical approximation of the Bessel functions of the first kind
For $x > 0, \alpha > 0 \in \mathbb{R}$, as $x \to \infty$: $$J_\alpha(x)\sim \sqrt{\frac{2}{\pi x}}\left(\cos \left(x-\frac{\alpha\pi}{2} - \frac{\pi}{4}\right) + \mathcal{O}\left(|x|^{-1}\...
1 vote
0 answers
243 views
Is it in theory possible to create a subexponential algorithm for solving discrete logarithms in multiplicative subgroups or within an Integer range?
As far I understand, when it comes to finite fields, Pollard rho and Pollard’s lambda are still the best algorithm for solving discrete logarithms in a multiplicative subgroup/suborder…. Index ...
- 129
0 votes
0 answers
138 views
Complexity of number of primes in arithmetic progression under $P=NP$
Fix distinct primes $q_1,\dots,q_t\in[2^{m-1},2^m]$ and integers $r_i\in[0,q_i-1]$ at every $i\in\{1,\dots,t\}$. Is there a way to exactly count the number of primes $a\equiv r_i\bmod q_i$ where $a\...
- 1
1 vote
1 answer
281 views
What is the fastest known algorithm for evaluating a homogeneous binary polynomial?
This question was initially posted on math.stackexchange.com, but there is no appropriate answer, hence I have the right to publish it here again. Let $f(x,y) = \sum_{i = 0}^d f_i x^i y^{d-i}$ be a ...
- 1,873
119 votes
11 answers
18k 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 ...
1 vote
0 answers
144 views
Construct an orthogonal simple polygon from a set of N mid–points
I am interested in the complexity of this problem: Input: Given N points on integer 2D grid (N is even) Question: Can we construct an orthogonal simple polygon from the set of N mid–points? Each mid–...
- 3,035
114 votes
10 answers
15k views
Analogues of P vs. NP in the history of mathematics
Recently I wrote a blog post entitled "The Scientific Case for P≠NP". The argument I tried to articulate there is that there seems to be an "invisible electric fence" separating the problems in P ...
5 votes
1 answer
315 views
What oracles make finding isomorphism (of finite structures) easy?
Below, all structures are finite, in a finite language, with underlying set an initial segment of the natural numbers. This has been edited to fix errors pointed out by Emil Jerabek in his answer ...
- 19.5k
5 votes
1 answer
413 views
Approximation of Hamiltonian cycles
Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most ...
- 53
0 votes
0 answers
79 views
Computational complexity of a system of linear diophantine equations with a non zero constraint
Given a system of linear diophanthine equations. What is the computational complexity of checking if the system has a solution or not or finding a solution if we have an additional constraint that ...
- 215
3 votes
1 answer
486 views
About Shor's quantum algorithm
I know very little about quantum computing, and I've been trying to understand Shor's algorithm for the factorization of an integer $N$. I'm following Computational Complexity — a modern approach by ...
- 2,359
1 vote
1 answer
295 views
The equation $ax^2 +by^2 =1 \mod P$ in cyclotomic field
Let $L$ be a cyclotomic field, and $P$ a prime ideal of $\mathcal{O}_L$. is there any symbol for the equation $ax^2 + by^2 =1 \mod P$ and if so, is it computable in polynomial time? if $a$ is ...
- 133
3 votes
1 answer
201 views
Complexity of membership problem in finite general linear group
$\DeclareMathOperator\GL{GL}$Suppose $G$ is a subgroup of $\GL(n,q)$ given by a list of generators. What is known about the complexity of the corresponding "membership problem", that is, the ...
- 2,359
13 votes
2 answers
659 views
Convergence of the sequence $s_{n+1}=s_n^2-s_{n-1}^2$
$s_{n+1}=s_n^2-s_{n-1}^2$, $s_0=\sqrt{x}$, $s_1=x$ This sequence seems simple, but is pretty confusing. If you try it with integers, you might think that it always diverges to infinity, but if you try ...
- 467
3 votes
1 answer
152 views
References: rigorous algorithms for elementary computations in base-b with complexity estimates
Definitions/Notation: Fix positive integers $b$ and $M$. Consider the set of real numbers which can be exactly expressed with $2M+1$ coefficients in base $b$, defined by $$\mathcal{X}(b,M):=\{x\in \...
- 4,942
0 votes
0 answers
91 views
Feasibility of $x$ in $g^x\equiv h\bmod N$
Finding $x$ in $g^x\equiv h\bmod p$ when $p$ is prime and $g$ is generator in multipicative group $\mathbb Z_p^\times$ is the discrete logarithm problem. It is not known to be in $P$. What is the ...
- 1
0 votes
0 answers
87 views
Is there a characterization of growth rates that are "regularly behaved"?
Assume every function is eventually nonnegative. In other words, we are interested in growth rates for measuring time complexity and such. $f = O(g)$ is equivalent to $\limsup \frac{f}{g} < \infty$,...
- 189
1 vote
0 answers
74 views
On computing $\mathsf{GCD }$ in $\mathsf{NC}$ if $2D$ linear Diophantine and coprimality are in $NC^1$
Consider have the promise problem of solving for integer solutions $u,v$ in the linear system $$au+bv=c$$ where the promise is $\mathsf{GCD}(a,b)=1$. Suppose this promise problem is in $NC^1$ and the ...
- 1
0 votes
0 answers
38 views
Are there known structural obstructions or theorems about partial-distance Katětov expansions that might fail to encode a TSP for large instances?
I have been experimenting with a partial-distance encoding of the decision version of the Traveling Salesman Problem (TSP) using a combination of Katětov–Urysohn ideas and what I have been calling “...
- 1