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,367 questions
5
votes
0
answers
70
views
Decision problem for finite (unordered) trees
One of the strongest results on the decidability of theories is Rabin's Tree Theorem. One way to state it is the following: tThe problem of deciding whether a sentence on the monadic second order (MSO)...
- 545
2
votes
0
answers
107
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
384
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.4k
1
vote
0
answers
115
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,464
1
vote
2
answers
318
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
561
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
109
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
181
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
224
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
45
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
166
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
148
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
77
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
309
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
216
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