Share Your Experience: Take the 2024 Developer Survey

# Tag Info

1 vote

### Is it known whether EXP is contained/not-contained in P/log?

EXP is not contained in P/log. This can be likely proved by direct diagonalization, extending the proof of $\let\R\mathsf\R{P\ne EXP}$ as in the time-hierarchy theorem, using the fact that there are ...
• 1,242

### Usage of matrix multiplication for distance products

Nice idea! But no, that doesn't work, alas. The problem with your approach is that the numbers become enormous, which makes matrix multiplication slow. It is tempting to say that the running time of ...
• 161k

### Polynomial solutions, one less

Suppose $L = \{(G_x, Y) \mid Y$ is the maximum or minimum vertex cover of $G_x\}$. This satisfies your requirements. Now let for $G_{x_0}$, we discard $Y_a$ as the maximum vertex cover (which is all ...
• 1,042
1 vote
Accepted

### Harder version of the k-partition problem

Short answer: It doesn't look like it. For your first example, hardness results for higher levels of the polynomial hierarchy, this problem is in NP for all $k$ (since a solution can be verified in ...
• 1,073
Accepted

### Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

Let's flip this around using the fact that $L$ is $\text{NP}$-hard iff $\overline{L}$ is $\text{coNP}$-hard. You want to show that $$\text{3-Col} \cup \overline{\text{4-Col}} \text{ is NP-hard}.$$ To ...
Accepted

• 13.6k