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

**109**

**11**answers

### On mathematical arguments against Quantum computing

**104**

**10**answers

### Analogues of P vs. NP in the history of mathematics

**84**

**27**answers

### Which popular games have been studied mathematically?

**73**

**6**answers

### Computational complexity of computing homotopy groups of spheres

**65**

**4**answers

### What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

**55**

**8**answers

### Example of a good Zero Knowledge Proof.

**53**

**10**answers

### The "sensitivity" of 2-colorings of the d-dimensional integer lattice

**52**

**2**answers

### Walsh Fourier Transform of the Möbius function

**46**

**7**answers

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

**46**

**3**answers

### Testing whether an integer is the sum of two squares

**43**

**8**answers

### Can a problem be simultaneously polynomial time and undecidable?

**43**

**8**answers

### Problems known to be in both NP and coNP, but not known to be in P

**43**

**7**answers

### What is the time complexity of computing sin(x) to t bits of precision?

**42**

**4**answers

### A curious process with positive integers

**41**

**2**answers

### How fast can we *really* multiply matrices?

**41**

**4**answers

### Why is "P vs. NP" necessarily relevant?

**38**

**10**answers

### What is the shortest program for which halting is unknown?

**34**

**5**answers

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

**34**

**1**answer

### How hard is reconstructing a permutation from its differences sequence?

**33**

**19**answers

### What is the easiest randomized algorithm to motivate to the layperson?

**33**

**4**answers

### Massive cancellations

**33**

**8**answers

### Is P=NP relevant to finding proofs of everyday mathematical propositions?

**33**

**1**answer

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

**32**

**2**answers

### The NP version of Matiyasevich's theorem

**30**

**4**answers

### Algebraic P vs. NP

**30**

**1**answer

### Guess that group via product queries

**30**

**1**answer

### An edge partitioning problem on cubic graphs

**29**

**3**answers

### Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?

**29**

**2**answers

### A combination of two well-known complexity problems

**28**

**4**answers

### A programming language that can only create algorithms with polynomial runtime?

**28**

**2**answers

### Simulating Turing machines with {O,P}DEs.

**28**

**1**answer

### How strong is this conjecture? $(Z/nZ)^*$ is generated by "small" elements

**28**

**2**answers

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

**27**

**1**answer

### Why is proving P != NP so hard?

**26**

**7**answers

### Solving NP problems in (usually) Polynomial time?

**26**

**10**answers

### Can We Decide Whether Small Computer Programs Halt?

**26**

**3**answers

### Why do statistical randomness tests seem so ad hoc?

**26**

**2**answers

### Is there a syntactic characterization for BPP, BQP, or QMA?

**26**

**0**answers

### Computational complexity of topological K-theory

**25**

**2**answers

### Who first dubbed them "expander graphs"?

**25**

**6**answers

### Are there any interesting examples of random NP-complete problems?

**25**

**4**answers

### Discrete logs vs. factoring

**25**

**1**answer

### Are sums of sequences decidable?

**25**

**4**answers

### Complexity of testing integer square-freeness

**24**

**3**answers

### Is the theory of categories decidable?

**24**

**5**answers

### Are there any computational problems in groups that are harder than P?

**24**

**4**answers

### How do we know that P != LINSPACE without knowing if one is a subset of the other?

**24**

**5**answers

### Are there complexity classes with provably no complete problems?

**24**

**3**answers

### Can one measure the infeasibility of four color proofs?

**24**

**1**answer