16
votes
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 ...
- 2,164
16
votes
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: ...
- 11.3k
7
votes
Common false beliefs in theoretical computer science
Superpolynomial time complexity cannot be in P. While this appears easy to believe, it is actually a false belief.
Formally, we may think that if $f(n)$ is a superpolynomial function, then ${\mathsf {...
5
votes
Common false beliefs in theoretical computer science
"When a problem is algorithmically undecidable, it means that it has a definite provable answer (yes or no) on all instances, but no unique algorithm is capable to reach this answer uniformly on ...
4
votes
Accepted
Uniqueness of the distribution maximizing the channel capacity
This conjecture is false. Here is a counterexample.
Suppose we have a binary symmetric channel:
$x_1 \rightarrow y_1$ with probability $1-\epsilon$ and $y_2$ with probability $\epsilon$,
$x_2 \...
- 24.3k
3
votes
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.
- 56
3
votes
Accepted
Easy to optimize but hard to evaluate
In paper [1], 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 ...
2
votes
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 ...
- 24.3k
1
vote
Accepted
Do such instances always admit a 3D matching?
How about the following counter-example?
$m=2$, $n=4$.
$A=\{a_1,a_2\}$, $B=\{b_1,b_2\}$, $C=\{c_1,c_2\}$.
$T=\{(a_1,b_1,c_1), (a_1,b_2,c_2), (a_2,b_1,c_2), (a_2,b_2,c_1)\}$.
With the partition
$A\cup ...
- 691
1
vote
Where and how did computers help prove a theorem?
A paper of mine with Gupta and Kumar titled On a bidirected relaxation for the MULTIWAY CUT problem was also based on running experiments. In fact we were trying to prove the converse of what we ended ...
1
vote
Where and how did computers help prove a theorem?
My recent paper with Karthik Chandrasekharan titled Hypergraph $k$-cut in deterministic polynomial time was based on extensive computational experiments. We explored different conjectures and ...
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