# Questions tagged [complexity]

The tag has no usage guidance.

4 questions
Filter by
Sorted by
Tagged with
2k views

### What exactly are the classes FP, FNP and TFNP?

In his book Computational Complexity, Papadimitriou defines FNP as follows: Suppose that $L$ is a language in NP. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced ...
936 views

### P/Poly vs Uniform Complexity Classes

It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization. What is the smallest uniform class C for which one can ...
It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$. Are there any known connections between the problems: P vs L, UP vs UL, NP ...
Consider a convex optimisation problem in the form \begin{align} f_0(x_1, \ldots, x_n) &\to \min \\ f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m \end{align} where \$f_0, f_1, \...