# 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; Komolgorov Complexity and so on.

**0**

**0**answers

### Partition of multisets of polynomials

**12**

**1**answer

### Would efficient factoring have any *other* useful applications?

**3**

**1**answer

### Computing moments of discrete probability distribution

**4**

**0**answers

### Is there a polynomial time algorithm for finding primes?

**0**

**0**answers

### Decidability of choosing delay in Takens' theorem

**2**

**1**answer

### Different quantum computation models equivalence

**3**

**1**answer

### Fastest way for certain rectangle matrix multiplication

**17**

**4**answers

### Languages beyond enumerable

**0**

**0**answers

### Asymptotic probability of a short path in the LEAF problem

**17**

**2**answers

### Kolmogorov complexity of classical music

**5**

**1**answer

### Lovász $\delta$ condition for LLL Algorithm

**2**

**1**answer

### Fast inverse of asymmetric diagonally dominant matrix with diagonal 1 and non-positive off-diagonals

**34**

**5**answers

### What are the strongest arguments for a genuine quantum computing advantage?

**7**

**0**answers

### Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs

**1**

**0**answers

### On perfect matchings on planar graphs - is there a linear time deterministic algorithm?

**0**

**2**answers

### Optimal path with multiple costs

**1**

**1**answer

### Complexity of edge coloring graphs with $\Delta(G) \ge n/3$ assuming the overfull conjecture

**8**

**0**answers

### Size of 3-SAT assignments

**3**

**1**answer

### Games and the right mathematical framework for GANs

**0**

**0**answers

### Exact Gaussian elimination of a rational matrix

**1**

**0**answers

### Does fraction-free Gaussian elimination use fractional row operations?

**10**

**1**answer

### What is known in general about the liquid transfer problem?

**2**

**0**answers

### A sub-logarithmic complexity in Analysis and N.Th

**15**

**3**answers

### What are the current breakthroughs of Geometric Complexity Theory?

**4**

**1**answer

### Polynomial size embeddings of toric varieties from polytopes?

**1**

**1**answer

### Complexity of games with graph classes

**0**

**0**answers

### 3-SAT family with $\omega(n^2)$ time complexity

**0**

**0**answers

### Reduce a recursively enumerable set to a recursive one not too sparsely

**2**

**1**answer

### Family of PTIME sets where it is hard to name elements

**0**

**0**answers

### On a deterministic primes search problem

**2**

**0**answers

### Minimum size of a Diophantine equation detecting the emptiness of a recursive set

**4**

**0**answers

### Determine the minimal elements of a Dynkin system generated by a finite set of finite sets

**13**

**3**answers

### Undecidable infinite analogs of NP-complete problems?

**12**

**1**answer

### Erdős multiplication problem revisited

**0**

**1**answer

### Computationally intractable orbit of a monoid action on a finite set

**46**

**7**answers

### Is it easy to produce hard-to-color graphs?

**1**

**1**answer

### Counting $\mathrm{mod}\:p$ solutions of Diophantine equation in two variables taking $O(p^2)$ time

**0**

**1**answer

### Is minimum weight vertex cover problem NP-easy? [closed]

**0**

**0**answers

### Can it be decided in advance if the relaxed (non-integer) solution of a integer program will result in low error when rounded?

**4**

**1**answer

### Is it intractable to locate a sequence of prime/not-prime bits?

**5**

**2**answers

### Complexity of rectangular matrix multiplication

**1**

**0**answers

### Literature about graph isomorphism and incidence matrix [closed]

**7**

**3**answers

### Complete problems for randomized complexity classes

**2**

**0**answers

### How to decide if an algebraic number is a root of a given polynomial?

**3**

**1**answer

### Is factorial computation known to be in a class smaller than $FEXP$?

**1**

**0**answers

### Maximum independent set in dense graphs

**7**

**1**answer

### $\mathit{NP}$-hard statements which are $\mathit{NP}$-complete under the Riemann Hypothesis

**0**

**0**answers

### Efficient Algorithm to Find Subset of Vectors Over $\mathbb{F}_q$ Living in Low Dimensional Subspace

**3**

**1**answer

### What is the computational cost in a neural network?

**2**

**0**answers