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 an so on.

**3**

**1**answer

### Higher roots modulo prime complexity best algorithm

**27**

**1**answer

### Is this conjecture strictly weaker than P=NP?

**1**

**2**answers

### Time functions of non-deterministic Turing machines (a better question)

**10**

**1**answer

### Real numbers with given complexity

**11**

**3**answers

### Determining if some permutation of a vector satisfies a system of linear equations

**1**

**1**answer

### Level sums, displacements: how to determine them efficiently?

**5**

**1**answer

### Time functions of non-deterministic Turing machines

**2**

**2**answers

### Complexity of 2D-Minkowski sum of non-convex polygons

**4**

**1**answer

### What is the time complexity for solving Diophantine equations of degree 2?

**2**

**1**answer

### Is this partition problem strongly NP-complete?

**3**

**2**answers

### Is there an efficient way to represent all non-simple cycles of a digraph up to the number of vertices?

**6**

**1**answer

### What is the complexity of determining if a knot group is $\mathbb{Z}$?

**1**

**0**answers

### descriptive complexity theory to attack computational complexity problems [closed]

**1**

**0**answers

### Bipartite clustering is NP-hard?

**12**

**0**answers

### Straight-line drawing of regular polyhedra

**87**

**9**answers

### On Mathematical Arguments Against Quantum Computing

**2**

**0**answers

### Factoring problem similar to $RSA$ structure that is possibly not $NP$ complete and not $coNP$ also?

**1**

**0**answers

### Is the partition of bipartite graphs NP-hard?

**0**

**0**answers

### Faster Mixed Integer Linear Programming Searchless Feasibility

**1**

**0**answers

### Complexity of computing roots in general rings

**21**

**2**answers

### Determining if a rational function has a subtraction-free expression

**0**

**1**answer

### Maximum partition of bipartite graph

**3**

**1**answer

### Incomparable NPI decision problems

**0**

**0**answers

### Number of bits in square representation in sieve techniques?

**0**

**0**answers

### On CNF forms with weight $d$ satisfying instances

**1**

**1**answer

### Non-invertible Karp reduction

**2**

**0**answers

### Clarification on FPTAS optimization in a paper

**0**

**0**answers

### Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$?

**0**

**0**answers

### Constructing integers with precise number of factors

**2**

**0**answers

### what is the relationship between the complexity of a function and the complexity of it's graph set?

**0**

**0**answers

### Fixed dimension Integer programming minus LLL in $NC$?

**1**

**1**answer

### Bit complexity of Barvinok's algorithm

**0**

**0**answers

### How hard is gapped satisfiability?

**4**

**1**answer

### What is the fastest way of finding a complement?

**1**

**0**answers

### Is there a problem that can be solved in each of a nested sequence of resource constraints, but not in their intersection?

**0**

**1**answer

### Is there fast algorithm for 3SUM?

**3**

**0**answers

### Deterministic procedure to find irreducible polynomials

**3**

**1**answer

### Algorithms for Fixing Sudokus

**0**

**0**answers

### Formalizing a projective additive construction of polytopes?

**1**

**2**answers

### On complexity of a combinatorial number theoretic problem?

**0**

**0**answers

### Minimum space needed to compute a binomial coefficient

**4**

**1**answer

### Time Complexity of the Word Problem for Finite Permutation Groups

**1**

**1**answer

### Complexity to decide for permutation group if every element fixed at most $k$ points

**1**

**2**answers

### Complexity of decision problem to decide if permutation group is $k$-transitive

**0**

**0**answers

### About Rademacher complexity

**0**

**0**answers

### Incompressibility formulations of computational complexity conjectures

**1**

**0**answers

### Complexity of conic optimization problems

**1**

**0**answers

### computing number of primes with congruence constraint

**1**

**1**answer

### Connections between algebraic semantics and computational complexity of a logic?

**1**

**0**answers