Search Results

You are right: formally P includes only decision problems. But many decision problems have corresponding optimization problems: find the size of the largest matching in a graph, find the length of the …

There is a polynomial time algorithm for finding Hamiltonian cycles on random graphs, that succeeds asymptotically with the same probability that a Hamiltonian cycle exists. Of course, this problem is …

The answer to your question is "no", although for natural problems that you might be thinking about, it may be a good heuristic that if the inner problem is NP hard, the whole problem is probably hard …

To continue along the lines of Deigo's answer, standard sample complexity bounds from learning theory tell you that if you are satisfied with finding a program which is "approximately correct", you do …

The problem of learning in the PAC model is really just a problem of combinatorial optimization: with a large enough sample size, finding a function $f \in C$ which has low prediction error is equival …

Here's a reference that you will want to look at: http://www.jstor.org/stable/10.2307/25442651 Mafia: A theoretical study of players and coalitions in a partial information environment Braverman, M. …

There cannot be significantly better algorithms for graphs with $O(n\log n)$ edges than there are for general graphs. This is because the Benczur-Karger cut sparsifier can take an arbitrary graph, and …

A fixed point of a best response function is a Nash equilibrium -- the fact that you do not have the payoff matrix cannot make the problem easier (since if you know the payoff matrix, you also know th …

No, its not known to be NP-complete, and it would be very surprising if it were. This is because its decision version is known to be in $\text{NP} \cap \text{co-NP}$. (Decision version: Does $n$ have …

I'm not sure I agree with your premise. I think in most papers, you will find short variable names: some of my personal favorites are $n$, $m$, $i$, $k$, $\epsilon$, and $\alpha$, each quite concise! …

One field with lots of non-monotonicity of problem complexity is property testing. Let $\mathcal{G}_n$ be the set of all $n$-vertex graphs, and call $P \subseteq \mathcal{G}_n$ a graph property. A gen …

There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "surprisi …

When you are coming up with an approximation algorithm for some NP-hard maximization problem, there are several values that you might care about: There is OPT, the optimal value of your problem, which …

Main stream game theorists are, I think, becoming much more open to contemporary work in the computer science community, so it may be less necessary to "make the case'' for algorithmic game theory tha …