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,365 questions
1
vote
0
answers
111
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,362
1
vote
2
answers
307
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
552
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
106
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
174
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
222
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
40
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
162
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
144
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
74
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
211
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 ...
- 263
1
vote
1
answer
101
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
153
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
485
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