We changed our privacy policy. Read more.

Questions tagged [complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
15
votes
2answers
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 ...
9
votes
3answers
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 ...
5
votes
0answers
851 views

Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

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 ...
8
votes
1answer
570 views

Is convex optimisation in P?

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, \...