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

**43**

**8**answers

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

**52**

**2**answers

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

**18**

**2**answers

### Explicit invariant of tensors nonvanishing on the diagonal

**16**

**2**answers

### Optimizing the condition number

**6**

**2**answers

### A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size

**109**

**11**answers

### On mathematical arguments against Quantum computing

**104**

**10**answers

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

**22**

**5**answers

### Can all convex optimization problems be solved in polynomial time using interior-point algorithms?

**16**

**6**answers

### SAT and Arithmetic Geometry

**15**

**3**answers

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

**46**

**7**answers

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

**34**

**1**answer

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

**26**

**7**answers

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

**21**

**2**answers

### Deep theorems and long proofs

**7**

**2**answers

### Building a Physical Model to Solve Sudoku

**11**

**3**answers

### Complexity of computing matrix rank over integers

**7**

**2**answers

### Computational complexity of calculating the nth root of a real number

**5**

**1**answer

### an algebraic variety for a boolean circuit

**28**

**2**answers

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

**17**

**1**answer

### Forcing over set theory versus forcing over arithmetic

**7**

**2**answers

### Conic hulls and cones

**5**

**1**answer

### Complexity for solving linear equations?

**12**

**1**answer

### Seeking references for finding primes infinitely often

**5**

**1**answer

### Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

**3**

**1**answer

### Relationship between P-noncomputable and P-random sets

**1**

**1**answer

### Finding the square root modulo n, when the factors of n are known

**1**

**1**answer

### relationship between corner tile and edge tile of wang tile

**6**

**1**answer

### Time functions of non-deterministic Turing machines

**6**

**1**answer

### Exact arithmetic for real algebraic numbers

**1**

**0**answers

### Maximum independent set in dense graphs

**43**

**7**answers

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

**41**

**2**answers

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

**24**

**3**answers

### Discrete Fourier Transform of the Möbius Function

**24**

**1**answer

### Evidence for integer factorization is in $P$

**23**

**4**answers

### Super-linear time complexity lower bounds for any natural problem in NP?

**30**

**1**answer

### Guess that group via product queries

**12**

**2**answers

### Connections between Complexity Theory & Set Theory

**29**

**3**answers

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

**19**

**2**answers

### Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$

**26**

**0**answers

### Computational complexity of topological K-theory

**25**

**2**answers

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

**18**

**4**answers

### Complexity of equitable partitions

**7**

**3**answers

### Decidable but nonrecursive sets

**16**

**8**answers

### Examples of ubiquitous objects that are hard to find?

**33**

**1**answer

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

**24**

**4**answers

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

**19**

**4**answers

### Enumeration and random selection

**11**

**0**answers

### The hardness of computing inverse

**6**

**2**answers

### the complexity of Lanczos method

**19**

**3**answers