# Tag Info

### 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 ...
• 3,688
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 ...
• 37.2k
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 ...
• 10.1k

### 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 &...
• 37.2k
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 ...

### 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 ...
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)
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.
• 109

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