# 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.

**6**

**0**answers

### Certificate for computation of ideal class group

**4**

**0**answers

### Algorithms to factorize words into product of powers

**1**

**0**answers

### Subgraph isomorphism problem with linear map

**1**

**0**answers

### Reporting uncoverable directed simple cycles in digraphs

**1**

**1**answer

### Could somebody suggest a way to determine if a parallelogram contains another parallelogram?

**1**

**0**answers

### Computational complexity of rate $\frac{1}{2}$ codes

**1**

**0**answers

### Promise version of minimum distance

**0**

**0**answers

### Time complexity of asymmetric sums of divisor function

**2**

**1**answer

### The complexity of expansion ratio (Cheeger constant) of a graph

**2**

**0**answers

### Evidence Barvinok's or Lenstra's algorithm can be improved

**1**

**0**answers

### Counting $\bmod 2$ number of vertices of sparsely represented polyhedra

**3**

**0**answers

### Modular counting of integral points under sparse non-negativity

**4**

**1**answer

### Finding a binary variable assignment to make a matrix with variables singular (over F_p)

**0**

**0**answers

### On complexity of a particular prime problem

**2**

**0**answers

### Computing bipartite matching of size $k$?

**1**

**0**answers

### Solution to system of linear equations

**5**

**3**answers

### Zero-knowledge proof for $P \ne NP$?

**4**

**0**answers

### Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

**1**

**1**answer

### Complexity of a Diophantine equation having $\leq1$ solutions

**10**

**0**answers

### Inverse polynomial map $\mathbb{Z}^2\to\mathbb{Z}^2$ growing faster than $2^{2^n}$

**1**

**0**answers

### Integrality of polyhedra

**3**

**0**answers

### Decidable equality for computable functions $\mathbb{N}\to\mathbb{N}$

**14**

**3**answers

### Exact coverability of $\mathbb{Z}_n$ by cyclic shifts of a given set — easy? NP-complete?

**5**

**0**answers

### Computing the zeta transform of a Boolean function: Space-time tradeoff

**0**

**0**answers

### Primality of $n$ bit integers in depth $n^\alpha$ under standard conjectures?

**0**

**1**answer

### What is the computational complexity of the calculation of $ \Psi(x) $?

**1**

**0**answers

### What is the computational complexity of solving a highly underdetermined system?

**0**

**1**answer

### Complexity of solving linear equations plus disequality constraints $a \ne b$

**1**

**1**answer

### Algorithms for Polynomials Over a Real Algebraic Number Field, a reference

**1**

**0**answers

### Complexity of checking if a set is an additive basis

**0**

**0**answers

### Deciding unimodular versus a singular matrix

**1**

**0**answers

### $\mathsf{NP}$ complete version of Skolem arithmetic

**0**

**0**answers

### Complexity of heaviest 2-optimal vertex-disjoint cycle covers

**0**

**1**answer

### Algorithmically decide if an algorithm has optimal time complexity [closed]

**0**

**1**answer

### What are the complexity classes of these problems about divisibility and coprimality?

**4**

**0**answers

### What is the complexity class of this problem without Cramer's conjecture?

**0**

**1**answer

### Maximize sum of edge weights on spanning tree

**1**

**0**answers

### Complexity of polynomial inequalities

**5**

**0**answers

### Are there any neusis-hard/neusis-complete problems?

**4**

**1**answer

### Bi-Hölder embeddings of finite metric spaces

**3**

**0**answers

### Games and the right mathematical framework for GANs

**0**

**0**answers

### Hardness of generating Gaussian distribution

**0**

**0**answers

### Computing Partial Theta Series

**10**

**1**answer

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

**1**

**0**answers

### what is the computational complexity of Louvain algorithm?

**3**

**0**answers

### Creating an $n\times n$ grid with specified $2\times2$ sums [closed]

**1**

**0**answers

### Reduction graph isomorphism to maximum independent set in very dense graph

**1**

**1**answer

### Complexity of solving $\sum_i A_i X B_i = C$

**3**

**0**answers

### Can equality of chromatic symmetric functions of two trees be checked in polynomial time?

**0**

**2**answers