# Tag Info

Accepted

### On theoretical aproaches for solving $\mathsf{SAT}$ in special cases

Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT. The first one that you are already familiar with is to restrict the types of the clauses that ...

### Easy to optimize but hard to evaluate

Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard. Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$. Task: ...

Accepted

### Example of decidable NP-hard problem that is not NP-complete

You can trivially consider NEXP-complete problems and they satisfy all 3 conditions that you're looking for. And by the Time Hierarchy Theorem, NP is strictly in NEXP.
Accepted

### Easy to optimize but hard to evaluate

In paper , there is a problem with the property that finding an optimal element takes polynomial time despite that computing the objective function values is NP-hard (it means that evaluating the ...
Accepted

### Fractional but not integer multi-commodity minimum cost flow

You can use the example for an undirected edge with unit capacities, but replace each undirected edge from A to B with a set of directed edges that look like this. Each edge has a unit capacity. And ...
1 vote
Accepted

1 vote

### Where and how did computers help prove a theorem?

Some recent results in state complexity were found with the help of systematic brute-force search for worst-case examples. This is doable because there are not too many deterministic finite automata ...
1 vote

### Where and how did computers help prove a theorem?

In 2018, Aubrey de Grey found a 1581-vertex, non-4-colourable unit-distance graph. This gives a lower bound of five for the famous Hadwiger-Nelson problem. He used a computer to verify that the graph ...

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