14 votes

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

L(2,1)-labeling is such a problem. The input is (just) a graph and we want to color it using the minimum number of colors so that neighboring vertices have colors that differ by at least 2 and ...
Michael Lampis's user avatar
7 votes
Accepted

Approaches to fast matrix multiplication and their limits

Their phrase in that paper "All work on matrix multiplication since 1986" is...an oversimplification. While it's true that what they cite are all the papers that have improved the state of ...
Joshua Grochow's user avatar
6 votes
Accepted

Complexity of determining whether the language of an P machine is empty

It's equivalent (under Turing reduction) to deciding whether the language of any given TM is empty. That is, it is co-RE-complete. This can be shown using a standard padding argument. Here are the ...
Neal Young's user avatar
  • 10.1k
5 votes

How does one "understand" complexity theory?

It's a nice question, but before partially answering it I want to question part of the premise. My main thesis here is that all mathematical fields are actually just loosely coherent collections of &...
Joshua Grochow's user avatar
3 votes
Accepted

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Another problem is Minimum Sum Edge Coloring. The input is a graph and the task is to compute a proper edge-coloring $\chi: E\to \mathbb{N}$ such that $\sum_{e\in E} \chi(e)$ is minimal. Here, proper ...
Christian Komusiewicz's user avatar
3 votes

How can I show a Gap-P problem is outside #P

This area has grown immensely in the 12 years since I asked the question. In particular, Ikenmeyer, Pak and Panova have shown that the squares of symmetric group characters are not in #(P), unless the ...
David E Speyer's user avatar
1 vote

Research masters programs in theoretical computer science (with a focus on complexity theory)

You may find this link useful https://www.cs.princeton.edu/~smattw/masters/masters.html (I would have commented, but my reputation is too low)
Matan Shtepel's user avatar
1 vote
Accepted

Sparsification and critical clauses in SAT

The partial answer existed in the paper, On the Complexity of k-SAT by Russell Impagliazzo and Ramamohan Paturi, 374 page, Theorem 3.
S. M.'s user avatar
  • 109

Only top scored, non community-wiki answers of a minimum length are eligible