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
36 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
46 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.5k
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
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
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
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_{\...
- 3,035
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
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
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 ...
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 ...
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 ...
- 401
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
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
2 votes
0 answers
161 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
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
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
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
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
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
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
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
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}\...
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
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
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
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
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
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
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
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
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
72 views
Extended Euclidean in $NC^1$ to $2D$ shortest vector problem in $NC$
$LLL$ algorithm is vectorized version of Extended Euclidean algorithm for $\mathsf{GCD}$. Even the $m=2$ dimensions case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector....
- 1
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
1 vote
0 answers
86 views
Reference request: Proof theory in $W_1^1$
Buss defined $V_2^1$ as a second-order bounded arithmetic corresponding to $\mathsf{PSPACE}$. Later, Skelley introduced $W_1^1$, a third-order bounded arithmetic of $\mathsf{PSPACE}$. Since the ...
- 11
3 votes
0 answers
139 views
What is the smallest known number of states that a one-way cellular automaton needs to be universal?
We know there is an elementary cellular automaton (ECA) with 2 states (Rule 110) that is universal, i.e. Turing-complete. One-way cellular automata (OCA's) are a subcategory of ECA's where the next ...
- 121
0 votes
0 answers
102 views
Complexity of evaluation of analytic functions
Given an analytic function $f(x)$ (say as combination of elementary functions and operators), is it possible to compute $n$ first bits of the value of the function on the whole interval $[a, b]$ ...
- 67
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
3 votes
0 answers
146 views
References on P vs NP under various axiomatic systems
I am teaching algorithms and theory of computation this semester and had the opportunity to dig a bit into the details of one way functions and the P vs NP problem. This problem has resisted attacks ...
- 31
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
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
1 vote
0 answers
56 views
Computing all roots of a function with square-root terms
Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function $$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$ Can we find all the ...
- 11
1 vote
0 answers
86 views
How computationally efficient are kernel tricks? [closed]
"If we compare to non-kernel polynomial regression it is O(Tnp) where is p is dimension of polynomial while kernel polynomial is O(n^2d) + O(T*n^2) where d is original number of attributes, ...
5 votes
0 answers
106 views
What is the maximal advantage of randomized over deterministic algorithms for approximation in the worst-case?
Let $X\subset Y$ be Banach spaces and $B_X:=\{x\in X: \|x\|_X\le1\}$ be the unit ball of $X$. The goal is to find an approximation of every element from $B_X$ with error measured in $Y$ by using at ...
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
414 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
226 views
Klondike Solitaire as an NP-complete game
I am not a mathematician. I am trying to understand if the paper "The complexity of solitaire" that shows this game is NP-complete also has a implicit assumption that a given hand can only ...
- 1