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
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
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.2k
12 votes
2 answers
1k views
Finding two rainbow spanning trees
Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour. Is the following problem NP-...
- 19.7k
5 votes
1 answer
198 views
Multi-head two-way finite automata versus logarithmic space
It is known that the languages decided by logarithmic-space Turing machines are exactly those decided by finite automata with multiple, bidirectional (2-way) scanning heads. Where could I find a proof?...
- 3,770
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 ...
CommunityBot
- 1
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 ...
- 38.3k
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\...
CommunityBot
- 1
1 vote
2 answers
357 views
Optimal path with multiple costs
Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. Given vertices $s$ and ...
CommunityBot
- 1
2 votes
1 answer
439 views
Determining strong base-orderability of a matroid
A matroid is said to be strongly base-orderable when for any two bases $B_1,B_2$ there exists a bijection $f:B_1 \mapsto B_2$ such that for any $X\subseteq B_1$ set $B_1 - X+ f(X)$ is also a base. ...
CommunityBot
- 1
1 vote
0 answers
189 views
What is the complexity of computing the p-values for a multivariate hypergeometric distribution
Are there efficient approaches to compute p-values of samples drawn from a multivariate hypergeometric distribution? Specifically, how does the complexity grow as a function of the "urn size" and the ...
- 2,702
1 vote
0 answers
317 views
Self-improvement property of optimization problems?
Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ...
- 2,653
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
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_{\...
- 8,286
0 votes
0 answers
41 views
What is the complexity of solving a constrained Algebraic Riccati Equation over a finite field?
Let $T=\left[\begin{array}{cc}A&B\\C&D\end{array}\right]$ be an $(m+n)\times(m+n)$ matrix over a finite field ${\mathbb F}_{q}$, where $A$ is $m\times m$ and $D$ is $n\times n$. Consider the ...
- 21
10 votes
5 answers
833 views
What is the relationship between "translation" and time complexity?
Consider the problem of deciding a language $L$; for concreteness, say that this is the graph isomorphism problem. That is, $L$ consists of pairs of graphs $(G, H)$ such that $G\simeq H$. Now the ...
- 3,770
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 ...
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 ...
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 ...
- 162k
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
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 ...
- 10.6k
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 ...
- 6,830
3 votes
2 answers
1k views
Is undirected short-simple-path-through-3-vertices decidable in polynomial time?
Consider the following language: $L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$. ($G$ ...
- 440
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 "...
- 1,103
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}...
- 2,456
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
8 votes
1 answer
329 views
Is the matrix multiplication exponent $\omega$ independent from the choice of the base field
The matrix multiplication exponent, usually denoted by $\omega_{F}$, is the smallest real number for which any two $n\times n$ matrices over a field $F$ can be multiplied together using ${\...
- 3,770
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 ...
- 14k
48 votes
11 answers
8k views
What is the shortest program for which halting is unknown?
In short, my question is: What is the shortest computer program for which it is not known whether or not the program halts? Of course, this depends on the description language; I also have the ...
- 14k
2 votes
1 answer
394 views
NP hard problems on UD graphs
I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard. Clark, Brent N.; ...
- 1,661
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
1 vote
0 answers
148 views
Canonical representation of binary decision trees in Ptime?
I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence. More precisely:...
- 1,661
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 ...
- 26
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
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? (...
- 530
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)>...
- 14k
25 votes
1 answer
2k views
Do we know how to determine the $2^{2020}$ decimal of $\sqrt{2}$?
In the case of $\dfrac{1}{7^{800}}$ it's easy, to find the $2^{2020}$ decimal, but what about the simplest of the irrational numbers. Question: Do we know how to determine the $2^{2020}$ decimal of $\...
- 6,934
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
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 ...
- 5,774
4 votes
0 answers
340 views
Circulant matrix inverse in $\mathrm{GF}(p)$
$\DeclareMathOperator\GF{GF}$For a polynomial $C(x)=c_0+\dots+c_n x^n$, consider a circulant matrix $C$ such that $$ C= \begin{pmatrix} c_0 & c_{n-1} & \cdots & c_2 & c_1 ...
- 67.2k
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}\...
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
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 ...
- 20.5k
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 ...
- 2,653
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 ...
- 38.3k
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 ...
- 741
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