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

**26**

**0**answers

### Computational complexity of topological K-theory

**21**

**0**answers

### Do we know how to determine the $2^{2020}$ decimal of $\sqrt{2}$?

**20**

**0**answers

### Straight-line drawing of regular polyhedra

**19**

**0**answers

### Checking Mertens and the like in less than linear time or less than $\sqrt{x}$ space

**19**

**0**answers

### Reference request: Parallel processor theorem of William Thurston

**16**

**1**answer

### Are there any natural theories T for which P=NP implies T proves P=NP?

**15**

**0**answers

### Complexity of a Fibonacci numbers discrete log variation

**15**

**0**answers

### Why should Algebraic Geometers and Representation Theorists care about Geometric Complexity Theory?

**15**

**0**answers

### Complexity classes for BSS machines

**15**

**0**answers

### Splay trees and Thompson's group $F$

**13**

**0**answers

### Regular languages of matrices and their generating functions

**13**

**0**answers

### Razborov's response to Almost Natural Proofs

**12**

**0**answers

### Does the Angel have to be really smart?

**12**

**0**answers

### Geometric complexity theory for finite fields

**12**

**0**answers

### Primes and Parity

**12**

**0**answers

### How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

**11**

**0**answers

### Primitive recursive and feasible presentations for nonstandard models of arithmetic

**11**

**0**answers

### Known obstruction for efficient computation of Stable homotopy groups?

**11**

**0**answers

### The hardness of computing inverse

**10**

**0**answers

### Collapsing the Linear Time Hierarchy and finite axiomatizability of bounded arithmetic

**10**

**0**answers

### Is Witten's new method of quantization useful for geometric complexity theory?

**9**

**0**answers

### Two-player independent set game

**9**

**0**answers

### Is there an efficient algorithm for testing isomorphism of projective planes?

**9**

**0**answers

### Is there a ``Ladner's Theorem" for the PH-vs-PSPACE scenario?

**9**

**0**answers

### Weighted Hamming distance

**8**

**0**answers

### Size of 3-SAT assignments

**8**

**0**answers

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

**8**

**0**answers

### Is recognizing if a Latin square is isotopic to its transpose more efficient than computing its symmetry group?

**8**

**0**answers

### Is Hankelability NP-hard?

**8**

**0**answers

### Ricocheting pinball-like shot: Complexity?

**8**

**0**answers

### Recognizing sequences sortable by transpositions?

**8**

**0**answers

### Can the isomorphism relation for countable models become harder when adding finitely many constants?

**8**

**0**answers

### Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

**7**

**0**answers

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

**7**

**0**answers

### Zero-knowledge proofs for answers to the $P=NP$ question

**7**

**0**answers

### Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere

**7**

**0**answers

### Does the problem of recognizing 3DORG-graphs have polynomial complexity?

**7**

**0**answers

### Surprising mathematical consequences of of $\mathbf{P} = \mathbf{NP}$

**7**

**0**answers

### Multidimensional hook length formula

**7**

**0**answers

### Why is solving polynomial systems NP hard?

**7**

**0**answers

### Can primes be (almost) random sequence in von Mises sense?

**7**

**0**answers

### Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?

**7**

**0**answers

### Is simultaneous diophantine approximation (in a weaker sense) NP hard?

**7**

**0**answers

### When is a reduction not a reduction?

**7**

**0**answers

### Feasible Type Theories

**7**

**0**answers

### Computational complexity of multiplication in a nilpotent group?

**7**

**1**answer

### Complexity of integer programming with added predicates

**6**

**0**answers

### Certificate for computation of ideal class group

**6**

**0**answers

### The provability logic of $I\Delta_0+\Omega_1 $ and complexity theory

**6**

**0**answers